教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本文是「宫水三叶的刷题日记」刷穿 LeetCode 系列第 436 篇仓库根目录位于gh_mirrors/lo/LogicStack-LeetCode围绕中等题「寻找右区间」展开。读完本文你将掌握一类区间配对问题的通用解法先通过「排序 二分」在 $O(n\log{n})$ 内为每个区间找到满足条件的右区间再进阶理解如何用「莫队思想 双指针」把构造答案的扫描成本从 $O(n^2)$ 优化到 $O(n)$并能在 Java、C、Python、TypeScript 四种语言中自由落地实现。题目背景与题意解析原题出自 LeetCode/431-440/436. 寻找右区间中等.md难度中等官方 Tag 为「排序」「二分」「双指针」「莫队算法」。题目描述给你一个区间数组intervals其中 $intervals[i] [start_i, end_i]$且每个 $start_i$ 都不同。区间 $i$ 的右侧区间可以记作区间 $j$并满足 $start_j \geqslant end_i$且 $start_j$ 最小化。返回一个由每个区间 $i$ 的右侧区间的最小起始位置组成的数组。如果某个区间 $i$ 不存在对应的右侧区间则下标 $i$ 处的值设为 $-1$。示例示例 1输入intervals [[1,2]] 输出[-1] 解释集合中只有一个区间所以输出 -1。示例 2输入intervals [[3,4],[2,3],[1,2]] 输出[-1,0,1] 解释对于 [3,4]没有满足条件的右侧区间。 对于 [2,3]区间 [3,4] 具有最小的右起点 对于 [1,2]区间 [2,3] 具有最小的右起点。示例 3输入intervals [[1,4],[2,3],[3,4]] 输出[-1,2,-1] 解释对于区间 [1,4] 和 [3,4]没有满足条件的右侧区间。 对于 [2,3]区间 [3,4] 有最小的右起点。数据范围提示$1 \leqslant intervals.length \leqslant 2 \times 10^4$$intervals[i].length 2$$-10^6 \leqslant start_i \leqslant end_i \leqslant 10^6$每个区间的起点都不相同题意转化理解本题的关键在于抓住两个要点只关心左端点对于区间 $i$其右端点 $end_i$ 是固定的我们只需要在所有区间中找到「左端点 $\geqslant end_i$」且「左端点值最小」的那个区间 $j$返回其原始下标$j$而不是左端点值本身。起点互不相同这一约束保证了「左端点最小」的候选区间是唯一的不会出现并列选择也让排序后的左端点序列天然没有重复值二分查找边界清晰。因此本题本质上是一个离线区间配对问题每个区间询问「谁是我右边最近的区间」而答案只由区间的左端点集合决定。解法一排序 二分思路推导为了方便我们称intervals为its。对于每个 $its[i]$ 而言我们需要在所有满足「$its[j][0] \geqslant its[i][1]$」的区间中找到 $its[j][0]$ 值最小的下标 $j$并将其记为 $ans[i]$。对于一个特定的 $its[i]$ 而言其右端点固定并且我们只关心目标位置的左端点。于是可以构造一个记录区间左端点的数组clone并将其排序同时为了记录每个左端点来自原序列中的哪个下标还需要额外记录原序列下标——即以 $(start, idx)$ 二元组的形式进行转存并根据start排序。之后从前往后处理每个 $its[i]$运用「二分」在clone中找到第一个满足左端点start大于等于 $its[i][1]$ 的成员clone[j]则clone[j][1]就是 $its[i]$ 的最右区间下标。二分细节为什么是找到第一个大于等于二分模板选择「查找左边界」风格lower_bound 语义若clone[mid][0] its[i][1]说明中点已经满足条件答案可能在左半区间含中点令r mid否则中点不满足条件令l mid 1。循环结束时l r此时还要再校验一次clone[r][0] its[i][1]是否真的成立因为当所有左端点都小于 $end_i$ 时指针会收敛到数组末尾即r n - 1而该位置的左端点并不满足条件此时应返回-1。完整代码Java 代码class Solution { public int[] findRightInterval(int[][] its) { int n its.length; int[][] clone new int[n][2]; for (int i 0; i n; i) clone[i] new int[]{its[i][0], i}; Arrays.sort(clone, (a,b)-a[0]-b[0]); int[] ans new int[n]; for (int i 0; i n; i) { int l 0, r n - 1; while (l r) { int mid l r 1; if (clone[mid][0] its[i][1]) r mid; else l mid 1; } ans[i] clone[r][0] its[i][1] ? clone[r][1] : -1; } return ans; } }C 代码class Solution { public: vectorint findRightInterval(vectorvectorint its) { int n its.size(); vectorpairint, int clone; clone.reserve(n); for (int i 0; i n; i) clone.push_back({its[i][0], i}); sort(clone.begin(), clone.end()); vectorint ans(n); for (int i 0; i n; i) { int l 0, r n - 1; while (l r) { int mid l r 1; if (clone[mid].first its[i][1]) r mid; else l mid 1; } ans[i] (clone[r].first its[i][1]) ? clone[r].second : -1; } return ans; } };Python 代码from typing import List class Solution: def findRightInterval(self, its: List[List[int]]) - List[int]: n len(its) clone [(its[i][0], i) for i in range(n)] clone.sort() ans [] for i in range(n): l, r 0, n - 1 while l r: mid l r 1 if clone[mid][0] its[i][1]: r mid else: l mid 1 ans.append(clone[r][1] if clone[r][0] its[i][1] else -1) return ansTypeScript 代码function findRightInterval(its: number[][]): number[] { const n its.length; const clone: [number, number][] its.map(([start, _], i) [start, i]); clone.sort((a, b) a[0] - b[0]); const ans: number[] new Array(n).fill(-1); for (let i 0; i n; i) { let l 0, r n - 1; while (l r) { const mid l r 1; if (clone[mid][0] its[i][1]) r mid; else l mid 1; } ans[i] clone[r][0] its[i][1] ? clone[r][1] : -1; } return ans; };复杂度分析时间复杂度排序复杂度为 $O(n\log{n})$对于每个 $its[i]$ 找到右区间需要进行一次二分复杂度为 $O(n\log{n})$。整体复杂度为 $O(n\log{n})$。空间复杂度$O(n)$用于存放clone数组与答案数组。从数据范围看$n \leqslant 2 \times 10^4$$O(n\log{n})$ 的复杂度完全足够即便面对 $10^5$ 级别的输入排序 二分依然高效。解法二双指针莫队思想从 $O(n^2)$ 到 $O(n)$ 的优化思路更进一步在解法一中我们并没有对求解询问的顺序进行调整这导致我们不得不每次都在整个左端点序列中进行二分。朴素处理询问的方式是每次对整个序列进行线性扫描复杂度为 $O(n^2)$。实际上如果我们按照「右端点从小到大」的顺序处理询问其每个询问对应的「最右区间的左端点」也具有单调特性当询问的 $end_i$ 单调不减时满足「左端点 $\geqslant end_i$」的候选位置只会向右移动不会回退因此可以用一个只增不减的指针j在排序后的左端点序列ss上扫描为每个询问找到第一个满足ss[j][0] end_i的位置。这正是莫队思想的精髓通过调整询问的处理顺序来减少扫描目标位置的指针移动次数。将其从「必然进行 $n^2$ 次移动」优化为「最多不超过 $n$ 次移动」从而将构造答案的复杂度从 $O(n^2)$ 优化为 $O(n)$。最后由于每个 $its[i]$ 只关心目标位置的「左端点」我们无须对某一段进行分块莫队算法的一般形态需要对区间分块排序而直接使用双指针实现即可——这是本题相对标准莫队问题的一个简化点。具体步骤构造两个二元组数组ss按 $(start_i, i)$ 组织并按start排序代表「候选左端点」es按 $(end_i, i)$ 组织并按end排序代表「询问顺序」。初始化答案数组ans为全-1指针j 0。按es的排序顺序即右端点从小到大处理每个询问(loc, idx)令j不断右移直到ss[j][0] loc若j n说明没有左端点满足条件ans[idx] -1否则ans[idx] ss[j][1]即该左端点对应的原始区间下标。完整代码Java 代码class Solution { public int[] findRightInterval(int[][] its) { int n its.length; int[][] ss new int[n][2], es new int[n][2]; for (int i 0; i n; i) { ss[i] new int[]{its[i][0], i}; es[i] new int[]{its[i][1], i}; } Arrays.sort(ss, (a,b)-a[0]-b[0]); Arrays.sort(es, (a,b)-a[0]-b[0]); int[] ans new int[n]; for (int i 0, j 0; i n; i) { int[] cur es[i]; int loc cur[0], idx cur[1]; while (j n ss[j][0] loc) j; ans[idx] j n ? -1 : ss[j][1]; } return ans; } }C 代码class Solution { public: vectorint findRightInterval(vectorvectorint its) { int n its.size(); vectorpairint, int ss, es; for (int i 0; i n; i) { ss.push_back({its[i][0], i}); es.push_back({its[i][1], i}); } sort(ss.begin(), ss.end()); sort(es.begin(), es.end()); vectorint ans(n, -1); for (int i 0, j 0; i n; i) { auto cur es[i]; int loc cur.first, idx cur.second; while (j n ss[j].first loc) j; ans[idx] (j n) ? -1 : ss[j].second; } return ans; } };Python 代码from typing import List class Solution: def findRightInterval(self, its: List[List[int]]) - List[int]: n len(its) ss [(its[i][0], i) for i in range(n)] es [(its[i][1], i) for i in range(n)] ss.sort() es.sort() ans [-1] * n j 0 for i in range(n): cur es[i] loc, idx cur[0], cur[1] while j n and ss[j][0] loc: j 1 ans[idx] -1 if j n else ss[j][1] return ansTypeScript 代码function findRightInterval(its: number[][]): number[] { const n its.length; const ss its.map(([start, _], i) [start, i]); const es its.map(([_, end], i) [end, i]); ss.sort((a, b) a[0] - b[0]); es.sort((a, b) a[0] - b[0]); const ans new Array(n).fill(-1); for (let i 0, j 0; i n; i) { const [loc, idx] es[i]; while (j n ss[j][0] loc) j; ans[idx] j n ? -1 : ss[j][1]; } return ans; };复杂度分析时间复杂度排序复杂度为 $O(n\log{n})$双指针构造答案的复杂度为 $O(n)$。整体复杂度为 $O(n\log{n})$。空间复杂度$O(n)$用于存放ss、es与ans。可以看到两种解法的渐近复杂度同为 $O(n\log{n})$但双指针版本在构造答案阶段将常数进一步压低排序之外只做了一次线性扫描实际运行往往更快代码也更为简洁。两种解法对比与选型建议对比维度排序 二分双指针莫队思想核心思想排序后对每个询问独立二分查找下界按右端点排序询问指针单调移动构造答案复杂度$O(n\log{n})$每次询问一次二分$O(n)$指针总移动次数不超过 $n$整体复杂度$O(n\log{n})$$O(n\log{n})$实现要点二分后需二次校验是否真的存在满足条件的区间利用右端点升序保证候选左端点指针单调适用场景通用性强适合任意询问顺序适合「询问条件随处理顺序单调」的离线问题选型建议若追求最稳的通用解法选「排序 二分」它对各种数据形态都成立且不易写错若想展示对莫队思想的掌握并追求更优常数选「双指针」版本——它把「调整询问顺序 单调指针」这一套路用到了极致是理解莫队算法思想的极佳入门案例。仓库视角本题在索引体系中的位置在「宫水三叶的刷题日记」仓库中本题被归入多个算法 Tag 索引可作为同类题目的延伸练习入口二分索引收录了 4. 寻找两个正序数组的中位数、35. 搜索插入位置、704. 二分查找 等与本题共用「在有序序列上二分查找边界」的核心范式双指针索引收录 15. 三数之和、11. 盛最多水的容器、475. 供暖器 等其中「供暖器」同样是「二分 双指针」双解法题与本题思路高度同源莫队算法索引本题是其中唯一收录的莫队思想应用示例可作为理解「调整询问顺序减少指针移动」这一思想的切入点。读者若想自行调试与提交代码可git clone本仓库gh_mirrors/lo/LogicStack-LeetCode在本地按 Tag 检索对应题解与代码。总结本题「寻找右区间」是区间类问题中非常典型的离线配对题目其核心收获有三点抓住关键维度每个区间只关心左端点集合右端点仅作为询问阈值参与比较将二维区间问题降维成一维查找问题排序 二分是万用底座$(start, idx)$ 二元组转存 排序 lower_bound 风格的左边界二分配合结束后的二次校验即可稳健通过莫队思想提供进阶视角通过按右端点排序询问让候选指针单调右移把构造答案的扫描代价从 $O(n^2)$ 降到 $O(n)$展现了「调整处理顺序以复用扫描进度」的通用优化哲学。掌握这两种解法后遇到同类「区间配对 / 最近右侧候选」问题如供暖器、区间合并变体等都可以直接迁移这套「排序 二分」或「排序 双指针」的骨架进行求解。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐LogicStack-LeetCode 题解精讲LeetCode 15. 三数之和排序 双指针LogicStack LeetCode 题解精讲LeetCode 15. 三数之和排序 双指针 本指南以「宫水三叶的刷题日记」刷穿 LeetCode教程文档AlgoNote 题解0436. 寻找右区间排序 二分查找求解区间后继问题AlgoNote 题解0436. 寻找右区间排序 二分查找求解区间后继问题 本篇基于「算法通关手册」AlgoNote 仓库的官方题解 find righ教程文档知识库leetcode 二分查找专题精讲上篇解空间、有序序列与折半中心思想leetcode 二分查找专题精讲上篇解空间、有序序列与折半中心思想 二分查找看似只有几行代码却是面试与竞赛中出错率最高的算法之一。本篇基于本仓库文档教程知识库上一篇终极B站会员购抢票指南如何用biliTickerBuy轻松搞定限量商品下一篇终极B站抢票指南用biliTickerBuy轻松搞定会员购限量商品创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考