企业官网建设流程全解析

• 教程
• 文档

本文是「宫水三叶的刷题日记」刷穿 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$
• 每个区间的起点都不相同

题意转化

理解本题的关键在于抓住两个要点：

1. 只关心左端点：对于区间 $i$，其右端点 $end_i$ 是固定的，我们只需要在所有区间中找到「左端点 $\geqslant end_i$」且「左端点值最小」的那个区间 $j$，返回其原始下标$j$，而不是左端点值本身。
2. 起点互不相同：这一约束保证了「左端点最小」的候选区间是唯一的，不会出现并列选择，也让排序后的左端点序列天然没有重复值，二分查找边界清晰。

因此，本题本质上是一个离线区间配对问题：每个区间询问「谁是我右边最近的区间」，而答案只由区间的左端点集合决定。

解法一：排序 + 二分

思路推导

为了方便，我们称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: vector<int> findRightInterval(vector<vector<int>>& its) { int n = its.size(); vector<pair<int, int>> clone; clone.reserve(n); for (int i = 0; i < n; i++) clone.push_back({its[i][0], i}); sort(clone.begin(), clone.end()); vector<int> 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 ans

TypeScript 代码

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]$ 只关心目标位置的「左端点」，我们无须对某一段进行分块（莫队算法的一般形态需要对区间分块排序），而直接使用双指针实现即可——这是本题相对标准莫队问题的一个简化点。

具体步骤

1. 构造两个二元组数组：
   • ss：按 $(start_i, i)$ 组织并按start排序，代表「候选左端点」；
   • es：按 $(end_i, i)$ 组织并按end排序，代表「询问顺序」。
2. 初始化答案数组ans为全-1，指针j = 0。
3. 按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: vector<int> findRightInterval(vector<vector<int>>& its) { int n = its.size(); vector<pair<int, 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()); vector<int> 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 ans

TypeScript 代码

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})$，但双指针版本在构造答案阶段将常数进一步压低：排序之外只做了一次线性扫描，实际运行往往更快，代码也更为简洁。

两种解法对比与选型建议

选型建议：若追求最稳的通用解法，选「排序 + 二分」，它对各种数据形态都成立且不易写错；若想展示对莫队思想的掌握并追求更优常数，选「双指针」版本——它把「调整询问顺序 + 单调指针」这一套路用到了极致，是理解莫队算法思想的极佳入门案例。

仓库视角：本题在索引体系中的位置

在「宫水三叶的刷题日记」仓库中，本题被归入多个算法 Tag 索引，可作为同类题目的延伸练习入口：

• 二分索引：收录了 4. 寻找两个正序数组的中位数、35. 搜索插入位置、704. 二分查找 等，与本题共用「在有序序列上二分查找边界」的核心范式；
• 双指针索引：收录 15. 三数之和、11. 盛最多水的容器、475. 供暖器 等，其中「供暖器」同样是「二分 + 双指针」双解法题，与本题思路高度同源；
• 莫队算法索引：本题是其中唯一收录的莫队思想应用示例，可作为理解「调整询问顺序减少指针移动」这一思想的切入点。

读者若想自行调试与提交代码，可git clone本仓库（gh_mirrors/lo/LogicStack-LeetCode），在本地按 Tag 检索对应题解与代码。

总结

本题「寻找右区间」是区间类问题中非常典型的离线配对题目，其核心收获有三点：

1. 抓住关键维度：每个区间只关心左端点集合，右端点仅作为询问阈值参与比较，将二维区间问题降维成一维查找问题；
2. 排序 + 二分是万用底座：$(start, idx)$ 二元组转存 + 排序 + lower_bound 风格的左边界二分，配合结束后的二次校验，即可稳健通过；
3. 莫队思想提供进阶视角：通过按右端点排序询问，让候选指针单调右移，把构造答案的扫描代价从 $O(n^2)$ 降到 $O(n)$，展现了「调整处理顺序以复用扫描进度」的通用优化哲学。

掌握这两种解法后，遇到同类「区间配对 / 最近右侧候选」问题（如供暖器、区间合并变体等），都可以直接迁移这套「排序 + 二分」或「排序 + 双指针」的骨架进行求解。

• 教程
• 文档