LeetCode 436. 寻找右区间

2022-04-10 HGNULB 约 12 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 436. 寻找右区间

题意分析

题目目标：给定一组区间，对每一个区间都要找出它的「右区间」——起点大于等于当前区间终点的所有区间中，起点最小的那一个，返回它在原数组中的下标；若不存在这样的区间则返回 -1。最终输出一个与输入等长的下标数组。
核心约束：题目保证每个区间的起点互不相同，这条约束消除了「起点相同该选哪个」的歧义，让「起点最小」的目标唯一。要返回的是原始下标而不是区间本身，这意味着一旦对数据做了重排，就必须把原下标一起带走，否则信息不可逆地丢失。查询是逐个区间进行的、共 n 次，而每次查询的形式都是「在一堆起点里找不小于某个值的最小者」——同一份数据被反复查询，这是典型的「预处理换查询效率」信号。区间数量上界在 $2 \times 10^4$ 量级，$O(n^2)$ 大约四亿次比较，风险很高，$O(n \log n)$ 才稳妥。
边界处理：区间自身也是候选，若某个区间满足起点大于等于自己的终点（长度为 0 的点区间就是如此），它的右区间可以是它自己；找不到时必须返回 -1 而不是抛异常或返回 0；只有一个区间时同样要走完整逻辑；起点可以是负数，比较和排序都不能假设非负。

解法：起点排序 + 二分

核心思路

最直接的做法是两层循环：对每个区间，扫一遍所有区间，在起点不小于当前终点的那些里挑起点最小的。这是 $O(n^2)$，在 n 达到两万时接近四亿次比较，很容易超时。瓶颈在于每次查询都从零开始线性搜索，完全没有利用「被查询的数据集合始终是同一份」这个事实。
观察查询的形式：我们要的是「在所有起点中，找第一个大于等于 target 的」。如果这些起点是乱序的，只能逐个看；但如果它们事先按升序排好，这个查询就变成了在有序序列上找下界，可以用折半查找在 $O(\log n)$ 内完成。而排序只需做一次，成本被 n 次查询摊薄。这就是用一次 $O(n \log n)$ 的预处理换取每次 $O(\log n)$ 查询的经典交换。
但排序会打乱原有的位置，而答案要的恰恰是原下标。解决办法是把每个起点和它的原下标绑成一个二元组一起排序——排序按起点比较，下标只是搭车的乘客。于是维护的不变量是：排序后的数组 pairs 中，pairs[k][0] 单调不减，且 pairs[k][1] 始终是 pairs[k][0] 这个起点在原输入中的下标。有了这个不变量，二分找到位置 k 之后，直接读 pairs[k][1] 就是要返回的答案。二分本身采用「找第一个满足条件的位置」这一形式：在左闭右开的搜索范围 [l, r) 上，不变量是「答案位置落在 [l, r] 之内」，每次取中点，若中点的起点已经不小于目标就把右界收到中点（中点自己可能就是答案，不能排除），否则把左界抬过中点。循环结束时 l 指向第一个满足条件的位置；若 l 等于 n，说明所有起点都比目标小，不存在右区间，答案为 -1。

正确性来自二分不变量：l 左侧的起点都严格小于 end，r 及其右侧的起点都满足条件；每次更新都保留分界点。退出时 l == r，它就是第一个不小于 end 的起点，也就是起点最小的右区间。

解题步骤

第一步：构造一个 n 行的辅助数组 pairs，每行存放 [起点, 原下标]。 为什么要显式带上原下标：排序会重排元素，而题目要的是原始位置，如果只排起点，排完之后就再也说不清某个起点原来在哪里了。为什么只带起点不带终点：查询的判据只涉及候选区间的起点，终点对候选没有任何筛选作用，多带一列纯属浪费。

第二步：按起点升序对 pairs 排序。 为什么升序而不是降序：目标是「第一个不小于 target 的位置」，升序排列才能让「满足条件」这个性质在数组上呈现出「前面一段全不满足、后面一段全满足」的单调分界形态，这是二分成立的前提。为什么不需要考虑排序稳定性：题目保证起点互不相同，不存在并列，任何排序结果都唯一。

第三步：对每个原区间 i，取出它的终点 end，在 pairs 上做一次「找下界」的二分，搜索范围初始化为左闭右开的 [0, n)。 为什么右界取 n 而不是 n-1：左闭右开的写法里，r 表示「答案的一个上界候选」，取 n 恰好能表达「所有元素都不满足条件」这一情形，让越界判断退化成一次简单的 l == n 比较，不需要额外的标志变量。为什么用 end 而不是 start 作为目标：右区间的定义就是起点不小于当前区间的终点。

第四步：二分体内，若 pairs[mid][0] >= end 则令 r = mid，否则令 l = mid + 1。 为什么满足条件时右界收到 mid 而不是 mid - 1：mid 自己就满足条件，它可能正是最靠左的那个答案，排除它会导致漏解；而左闭右开的语义下 r = mid 表示「答案在 mid 或它左边」，恰好保留了这种可能。为什么不满足时左界要跨过 mid：mid 的起点比 end 小，它以及它左边的所有元素都不可能是答案，直接跳过是安全的，同时保证区间严格缩短、循环必然终止。为什么中点写成 l + (r - l) / 2：避免 l + r 在大下标时溢出，这是二分的固定写法。

第五步：循环结束后若 l == n 则写入 -1，否则写入 pairs[l][1]。 为什么 l == n 就代表无解：二分的不变量保证退出时 l 是第一个满足条件的位置，等于 n 意味着搜索范围内没有任何元素满足，即所有起点都严格小于 end。为什么可以直接取 pairs[l][1]：排序后 l 是满足条件的最左位置，而数组按起点升序，最左即起点最小，正是题目要的「起点最小的那个」；第二列存的就是它的原下标。

以 intervals = [[3,4],[2,3],[1,2]] 走一遍。 先构造 pairs：区间 0 的起点是 3，得 [3,0]；区间 1 的起点是 2，得 [2,1]；区间 2 的起点是 1，得 [1,2]。按起点升序排序后 pairs 为 [[1,2],[2,1],[3,0]]。现在逐个查询。查询 i = 0：end = 4，二分范围 [0,3)。第一轮 mid = 1，pairs[1][0] = 2 < 4，令 l = 2；第二轮 l = 2、r = 3，mid = 2，pairs[2][0] = 3 < 4，令 l = 3；此时 l = r = 3 退出，l 等于 n，写入 -1。正确——没有任何区间的起点不小于 4。查询 i = 1：end = 3，范围 [0,3)。第一轮 mid = 1，pairs[1][0] = 2 < 3，l = 2；第二轮 mid = 2，pairs[2][0] = 3 >= 3，r = 2；此时 l = r = 2 退出，pairs[2][1] = 0，写入 0。正确——区间 0 是 [3,4]，起点 3 恰好等于查询终点 3，是唯一候选。查询 i = 2：end = 2，范围 [0,3)。第一轮 mid = 1，pairs[1][0] = 2 >= 2，r = 1；第二轮 l = 0、r = 1，mid = 0，pairs[0][0] = 1 < 2，l = 1；此时 l = r = 1 退出，pairs[1][1] = 1，写入 1。正确——候选有起点为 2 的区间 1 和起点为 3 的区间 0，起点最小的是区间 1。最终结果 [-1, 0, 1]，与预期一致。这个例子还顺带验证了「等号必须包含在条件里」——查询 i = 1 时若把判据写成严格大于，就会错过起点恰好等于 3 的区间 0 而返回 -1。

代码实现

import java.util.Arrays;

// 核心实现：起点排序 + 二分，维护必要状态并避免重复处理。
class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        int[][] pairs = new int[n][2];
        for (int i = 0; i < n; i++) {
            pairs[i][0] = intervals[i][0];
            pairs[i][1] = i;
        }
        Arrays.sort(pairs, (a, b) -> Integer.compare(a[0], b[0]));

        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            int end = intervals[i][1];
            int l = 0;
            int r = n;
            while (l < r) {
                int mid = l + (r - l) / 2;
                if (pairs[mid][0] >= end) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            if (l == n) {
                res[i] = -1;
            } else {
                res[i] = pairs[l][1];
            }
        }
        return res;
    }
}

import "sort"

// 核心实现：起点排序 + 二分，维护必要状态并避免重复处理。
func findRightInterval(intervals [][]int) []int {
	n := len(intervals)
	pairs := make([][]int, n)
	for i := 0; i < n; i++ {
		pairs[i] = []int{intervals[i][0], i}
	}
	sort.Slice(pairs, func(i, j int) bool { return pairs[i][0] < pairs[j][0] })

	res := make([]int, n)
	for i := 0; i < n; i++ {
		end := intervals[i][1]
		l, r := 0, n
		for l < r {
			mid := l + (r-l)/2
			if pairs[mid][0] >= end {
				r = mid
			} else {
				l = mid + 1
			}
		}
		if l == n {
			res[i] = -1
		} else {
			res[i] = pairs[l][1]
		}
	}
	return res
}

复杂度分析

时间复杂度：$O(n \log n)$。凭什么：构造 pairs 是 $O(n)$，排序是 $O(n \log n)$，随后对 n 个区间各做一次 $O(\log n)$ 的二分共 $O(n \log n)$，三部分相加由排序与查询共同主导。

空间复杂度：$O(n)$。凭什么：额外开了一个 n 行的 pairs 数组来承载「起点 + 原下标」，这是排序不丢失位置信息的必要代价；结果数组是题目要求的输出；此外只有常数个标量，排序本身在 Java 中对对象数组使用归并排序还需 $O(n)$ 的临时空间，量级不变。

关键点总结

「同一份数据被查询多次」是把线性扫描升级为排序加二分的标准信号。判断依据是查询次数与数据规模同阶——一次预处理的成本能被摊薄到每次查询上，总代价才会从 $O(n^2)$ 降到 $O(n \log n)$。

排序会摧毁位置信息，凡是答案需要原下标的题，都必须在排序前把下标绑定进元素。这个「值与下标打包」的动作是数组类题目里最容易遗漏也最容易调试半天的一步。

「找第一个不小于 target 的位置」是二分最常用的变体，建议固定用左闭右开加 r = mid / l = mid + 1 的模板：满足条件时保留 mid，不满足时跨过 mid，退出时 l 即答案，l == n 天然表示无解。把这套模板背成肌肉记忆，能同时覆盖下界、上界、插入位置等一系列问题。

判据里的等号要从题意直接读出来。本题说的是「起点大于等于终点」，所以条件必须含等号；区间自身在退化为点区间时会成为自己的答案，这不是 bug 而是题意允许的合法结果。

面试视角：这题是考察「排序 + 二分」组合的典型题，面试官通常会先让你说出 $O(n^2)$ 暴力，再引导你发现查询形式的重复性。回答时要主动点明两件事——为什么必须携带原下标、二分找的是下界而非精确匹配。常见追问是「能不能用有序表代替手写二分」（Java 可用 TreeMap 的 ceilingEntry，一行搞定，但面试通常要求手写二分以展示边界掌控）以及「如果起点允许重复怎么办」（需要额外约定选哪个下标，或改用能返回多值的结构）。

易错点总结

错误写法：排序时只对起点数组排序，不携带原下标。用例 intervals = [[3,4],[2,3],[1,2]] → 排序后拿到的是排序位置 2、1、0 而非原下标，输出 [-1,2,1]，与正确答案 [-1,0,1] 不符。

错误写法：二分判据写成严格大于 pairs[mid][0] > end。用例 intervals = [[3,4],[2,3],[1,2]] → 查询区间 1 时起点恰好等于 3 的候选被跳过，输出 [-1,-1,1]，正确答案第二位应是 0。

错误写法：满足条件时写 r = mid - 1 却保持左闭右开的循环条件。用例 intervals = [[1,2],[2,3]] → mid 本身是唯一答案却被排除，查询区间 0 时返回 -1，正确答案是 1。

错误写法：右界初始化为 n - 1 并用 l <= r 循环，退出后直接取 pairs[l]。用例 intervals = [[1,4]] → 无解时 l 越过 r 变成 1，访问 pairs[1] 数组越界崩溃，而正确输出应是 [-1]。

风险写法：中点写成 (l + r) / 2，比较器用 a[0] - b[0]。本题规模下中点安全，但通用模板应使用 l + (r-l)/2 与 Integer.compare，避免约束扩大后溢出。

错误写法：用当前区间的起点而非终点去二分。用例 intervals = [[1,4],[2,3]] → 查询区间 0 时以 1 为目标找到自己，输出 0，而正确答案是 -1，因为没有任何起点不小于终点 4。

错误写法：为避免选到自己而显式跳过下标相同的候选。用例 intervals = [[1,1],[3,4]] → 点区间 [1,1] 的合法答案就是它自己 0，跳过后错误地返回 1。

错误写法：不排序直接对原数组二分。用例 intervals = [[3,4],[2,3],[1,2]] → 起点序列 3、2、1 并非升序，二分的单调前提不成立，返回值随机，查询区间 2 可能得到 -1 而正确答案是 1。

错误写法：无解时写入 0 而非 -1。用例 intervals = [[1,2]] → 输出 [0]，被判为把自己当成了右区间，正确答案是 [-1]。

错误写法：Go 的 sort.Slice 比较函数使用 <=。比较函数必须表示严格小于；否则相等元素连与自身比较都可能返回真，破坏排序契约。

相似题目

题目	难度	考察点
56. 合并区间	中等	同样先按起点排序，但后续是线性合并重叠而非二分查询
57. 插入区间	中等	在已有序的区间集合里插入并合并，考察三段式扫描的边界划分
986. 区间列表的交集	中等	两个有序区间列表求交，用双指针同步推进代替二分
646. 最长数对链	中等	同样是「找下一个可衔接的区间」，但目标是最长链，按终点排序做贪心更优
1235. 规划兼职工作	困难	排序加二分之上再叠一层动态规划，二分用于定位上一个不冲突的任务
300. 最长递增子序列	中等	二分找下界的另一经典应用，维护的是一个可替换的末尾值数组