LeetCode 646. 最长数对链

2021-07-24 HGNULB 约 7 分钟

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

分类

题目描述

✅ 646. 最长数对链

题意分析

要什么：给一堆数对，每个数对满足左端小于右端。数对 [c, d] 能接在 [a, b] 之后当且仅当 b < c。求能串起来的最长链的长度。
约束透露的信号：题目没有要求保持输入顺序，明确说了可以任意选取并重新排列——这句话是整题的钥匙，它把「子序列问题」松绑成「子集问题」，从而允许我们先排序再决策。此外只问链的长度、不问具体是哪条链，说明不需要记录方案。数对数量到 $10^3$ 以上，$O(n^2)$ 勉强能过但不是最优解。
边界：接续条件是严格的 b < c，端点相等（b == c）不允许接续；端点可以是负数，任何「初值设 0」的写法都不安全；至少有一个数对，答案下界是 1；不同数对可能完全重叠或互相包含。

解法：按右端点排序的贪心

核心思路

先看暴力：把数对当成一个可以任意重排的集合，枚举子集是 $2^n$；退一步用动态规划——按左端点排序后设 f[i] 为以第 i 个数对结尾的最长链，转移是 f[i] = max(f[j]) + 1（j 的右端小于 i 的左端），时间 $O(n^2)$。这是对的，但两两比较里有大量冗余。
瓶颈在于：动态规划把「以谁结尾」这件事记了 n 份，而实际上我们只关心「当前链末尾的右端点有多小」——右端点越小，后面能接的数对越多，链末尾的其它信息（左端点是多少、链上具体是谁）对未来完全没有影响。
这就引出贪心的交换论证：在所有最长链中，一定存在一条，它的第一个数对是全局右端点最小的那个。理由是把任意最优链的首元素换成右端点最小的数对，后续元素依然接得上（右端点只会变小，约束只会更松），链长不变。对剩余部分递归应用同一论证，就得到「按右端点升序扫描、能接就接」的策略。
由此写下要维护的不变量：扫描到任意位置时，count 是仅考虑已扫描过的数对所能构成的最长链长度，而 curEnd 是在长度达到 count 的所有链中，最小的那个末尾右端点。「长度最大」与「同长度下末尾最小」这两条必须一起成立，后者保证当前状态对未来最不设限，贪心才不会因为一时选错而堵死后路。

解题步骤

按右端点升序排序。为什么是右端点而不是左端点：链的可扩展性只由末尾的右端点决定，右端点越小留给后续的空间越大；按左端点排序会让一个左端很小但右端极大的数对抢先占位，把后面一串小数对全部挤掉。

把 count 置 0、curEnd 置为一个足够小的哨兵值。为什么哨兵不能写 0：端点允许为负，若某个数对是 [-5, -3]，用 0 当初值会让 -5 > 0 为假，第一个数对就被跳过，答案凭空少 1。

依次扫描每个数对，若 pair[0] > curEnd 就令 count++ 并把 curEnd 更新为 pair[1]。为什么是严格大于：题目定义的接续条件是 b < c，端点相等不算合法接续，写成 >= 会把 [1,2] 和 [2,3] 误判为可串联。为什么不满足时什么都不做：当前数对的右端点必然不小于 curEnd（已排序），把它换进来既不能加长链，也不能让末尾更小，纯属有害无益。

返回 count。为什么不需要回头修补：不变量保证每一步的 count 都是当前前缀的最优解，扫完最后一个数对时它自然就是全局最优。

以 pairs = [[1,2], [7,8], [4,5]] 走一遍。按右端点升序排序后变成 [1,2]、[4,5]、[7,8]。初始 count = 0、curEnd 为哨兵极小值。第一个 [1,2]：1 > 极小值 成立，count = 1，curEnd = 2。第二个 [4,5]：4 > 2 成立，count = 2，curEnd = 5。第三个 [7,8]：7 > 5 成立，count = 3，curEnd = 8。返回 3。再换一组会被跳过的数据体会一下：pairs = [[1,2], [2,3], [3,4]] 排序后不变，选中 [1,2] 后 curEnd = 2，[2,3] 的左端 2 不大于 2 被跳过，[3,4] 的左端 3 大于 2 被选中，答案为 2——这正是「端点相等不能接」的直接体现。

代码实现

// 核心实现：按右端点排序的贪心，维护必要状态并避免重复处理。
class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> a[1] - b[1]);

        int count = 0;
        int curEnd = Integer.MIN_VALUE;
        for (int[] pair : pairs) {
            if (pair[0] > curEnd) {
                count++;
                curEnd = pair[1];
            }
        }
        return count;
    }
}

// 核心实现：按右端点排序的贪心，维护必要状态并避免重复处理。
func findLongestChain(pairs [][]int) int {
    sort.Slice(pairs, func(i, j int) bool {
        return pairs[i][1] < pairs[j][1]
    })

    count := 0
    curEnd := -1 << 60

    for _, pair := range pairs {
        if pair[0] > curEnd {
            count++
            curEnd = pair[1]
        }
    }

    return count
}

复杂度分析

时间复杂度：$O(n \log n)$。凭什么：排序占 $O(n \log n)$ 且是全式的主项；之后只有一趟线性扫描，每个数对做一次比较和至多一次常数赋值。

空间复杂度：$O(\log n)$ 到 $O(n)$，取决于排序实现。凭什么：算法本身只用 count 和 curEnd 两个标量；Go 的 sort.Slice 是原地快排只需 $O(\log n)$ 递归栈，Java 对对象数组使用归并排序需要 $O(n)$ 辅助空间。

关键点总结

「可任意重排」是区间贪心的许可证：题面里出现这四个字，就该立刻从「按下标 DP」切换到「排序 + 贪心」。反过来若要求保持原顺序，本题就退化成最长上升子序列式的 DP，贪心不再成立。

区间调度类问题的排序键几乎总是右端点，因为可扩展性只由右端点决定。这条经验能直接迁移到「无重叠区间」「用最少箭引爆气球」「会议安排」等一整族题。

贪心的正确性要靠交换论证说清：把任意最优解的首元素替换成贪心选的那个，解仍然合法且不变差。面试里只说「按右端点排就对了」是拿不到分的，必须给出这句论证。

不变量要写成两句话：「长度最大」+「同长度下末尾最小」。第二句才是贪心不翻车的真正原因，也是面试官追问「为什么不会选错」时的标准答案。

面试视角：建议主动交代「还有一个 $O(n^2)$ 的 DP 解法，它在需要输出具体方案或接续条件更复杂时更通用」，展示你知道贪心的适用边界，而不是只会套模板。

易错点总结

错误写法：按左端点排序；用例 [[1, 100], [2, 3], [4, 5]] → 先选中跨度极大的 [1, 100]，curEnd 变成 100，后两个都接不上，返回 1，正确答案是 2。

错误写法：curEnd 初始化为 0；用例 [[-10, -8], [-7, -5]] → 第一个数对的左端 -10 不大于 0 被跳过，第二个的左端 -7 也不大于 0 被跳过，返回 0，正确答案是 2。

错误写法：接续判断写成 pair[0] >= curEnd；用例 [[1, 2], [2, 3]] → 误认为 2 能接在 2 后面，返回 2，正确答案是 1。

错误写法：排序比较器写成 a[0] - b[0] 却仍用右端点做贪心；用例 [[3, 4], [1, 2]] → 顺序没有按可扩展性排好，[3,4] 抢先入选后 [1,2] 因左端 1 不大于 4 被丢弃，返回 1，正确答案是 2。

错误写法：不满足条件时也更新 curEnd = pair[1]；用例 [[1, 2], [1, 3], [4, 5]] → 排序后 [1,2] 入选使 curEnd = 2，接着 [1,3] 未入选却把 curEnd 改成 3，最后 [4,5] 虽仍能入选但在更极端数据（如末尾右端为 100 的干扰项）下会把后续全部挡住，答案偏小。

错误写法：用 Integer.MIN_VALUE 当哨兵但比较时写成 pair[0] - curEnd > 0；用例 [[-1000, -999], ...] → 减法在极小值上溢出，比较结果反转，第一个数对被跳过。

错误写法：排序比较器写成 (a, b) -> a[1] - b[1] 而端点是可能溢出的大整数；用例端点接近 int 上下界 → 相减溢出导致比较器不满足传递性，Java 抛出 Comparison method violates its general contract。本题端点范围小不会触发，但这是同类写法的通病。

错误写法：把答案初始化为 1 并从第二个数对开始扫；用例只有一个数对 [[1, 2]] → 恰好正确；但用例 [[5, 6], [1, 2]] 排序后第一个是 [1,2]，跳过它直接从 [5,6] 开始判断且 curEnd 未被正确设为 2，逻辑与不变量脱节，答案不可控。

错误写法：认为「链」必须使用输入中相邻的数对，于是只在原数组顺序上做扫描；用例 [[3, 4], [1, 2]] → 不排序直接扫，[3,4] 入选后 [1,2] 接不上，返回 1，正确答案 2。

相似题目

题目	难度	考察点
435. 无重叠区间	中等	同一套右端点贪心，但求的是需要删除的区间数，且区间端点相接算不重叠
452. 用最少数量的箭引爆气球	中等	求的是分组数而非链长，边界闭合导致判断条件从严格大于变成大于等于
300. 最长递增子序列	中等	顺序不可打乱，贪心失效，只能用 DP 或贪心加二分维护尾值数组