题目描述
这是 LeetCode 上的「646. 最长数对链」，难度为「中等」。
Tag : 「贪心」、「排序」、「二分」、「序列 DP」、「LIS」
给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
现在，我们定义一种跟随关系，当且仅当 b < c 时，数对
才可以跟在
后面。我们用这种形式来构造一个数对链。
给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例：
代码语言：javascript复制输入：[[1,2], [2,3], [3,4]]
输出：2
解释：最长的数对链是 [1,2] -> [3,4]
提示：
- 给出数对的个数在
范围内。
排序 贪心 DP
起始先将 pairs 根据第一维排升序（或直接双关键字排升序）。
考虑定义
为以
为结尾的最长数对链长度，所有
中的最大值为答案。
不失一般性考虑
该如何转移：不难发现
为所有满足「下标范围在
，且
」条件的
的最大值。
但实际上，我们只需要从
开始往回找，找到第一个满足
的位置
即可。
容易证明该做法的正确性：假设贪心解（该做法）找到的位置
不是最优位置，即存在比
更小的合法下标
满足
。根据我们的排序规则必然有
的性质，则可知
必然可以代替
接在原本以
为结尾的最优数链上（最优数链长度不变，结果不会变差），则至少有
。
代码：
代码语言：javascript复制class Solution {
public int findLongestChain(int[][] pairs) {
Arrays.sort(pairs, (a,b)->a[0]-b[0]);
int n = pairs.length, ans = 1;
int[] f = new int[n];
for (int i = 0; i < n; i ) {
f[i] = 1;
for (int j = i - 1; j >= 0 && f[i] == 1; j--) {
if (pairs[j][1] < pairs[i][0]) f[i] = f[j] 1;
}
ans = Math.max(ans, f[i]);
}
return ans;
}
}
- 时间复杂度：排序的复杂度为
；不考虑剪枝效果 DP 复杂度为
。整体复杂度为
- 空间复杂度：
排序 贪心 DP（优化转移）
根据上述分析，我们知道对于一个特定的
而言，其所有合法（满足条件
）的前驱状态
必然是非单调递增的。
根据 LIS 问题的贪心解的思路，我们可以额外使用一个数组记录下特定长度数链的最小结尾值，从而实现二分找前驱状态。
具体的，创建
数组，其中
代表数链长度为
时结尾元素的第二维最小值为
。
如此一来，当我们要找
的前驱状态时，等价于在
数组中找满足「小于
」的最大下标。同时，我们不再需要显式维护
数组，只需要边转移变更新答案即可。
❝不了解
LIS问题的同学可以看前置
