LeetCode646-最长数队链
最长数队链
给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例：
输入：[[1,2], [2,3], [3,4]]
输出：2
解释：最长的数对链是 [1,2] -> [3,4]
贪心
解题思路
根据题意知要找最长的数队链,即找满足 一个数组中第一个数大于另一个数组中第二个数 条件的最多的数组个数。
那么要挑选最长数对链的第一个数对时，最优的选择是挑选第二个数字最小的，这样能给挑选后续的数对留下更多的空间。挑完第一个数对后，要挑第二个数对时，也是按照相同的思路，是在剩下的数对中，第一个数字满足题意的条件下，挑选第二个数字最小的。
解题步骤
- 将输入按照第二个数字排序
- 遍历pairs。判断pairs中数队第一个数字是否能满足大于前一个数对的第二个数字，若满足变量rs+1
class Solution {
public int findLongestChain(int[][] pairs) {
int curr = Integer.MIN_VALUE, rs = 0;
Arrays.sort(pairs, (a, b) -> a[1] - b[1]);
for (int[] p : pairs) {
if (curr < p[0]) {
curr = p[1];
rs++;
}
}
return rs;
}
}
时间复杂度：O(nlogn),排序时间复杂度
空间复杂度：O(logn),排序空间复杂度
动态规划
解题思路
- 定义 dp[i] 为以pairs[i] 为结尾的最长数对链的长度。
- 计算 dp[i] 时，可以先找出所有的满足pairs[i][0]>pairs[j][1] 的 j，并求出最大的dp[j]，dp[i] 的值即可赋为这个最大值加一。
- 注意：这种动态规划的思路要求计算dp[i] 时，所有潜在的 dp[j] 已经计算完成，可以先将 pairs 进行排序来满足这一要求。
class Solution {
public int findLongestChain(int[][] pairs) {
int n = pairs.length;
Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (pairs[i][0] > pairs[j][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return dp[n - 1];
}
}
时间复杂度：O(n^2)
空间复杂度：O(n)