LeetCode646-最长数队链

最长数队链

给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。

现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。

给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

示例：

输入：[[1,2], [2,3], [3,4]]
输出：2
解释：最长的数对链是 [1,2] -> [3,4]
1
2
3

贪心

解题思路
根据题意知要找最长的数队链,即找满足 一个数组中第一个数大于另一个数组中第二个数 条件的最多的数组个数。

那么要挑选最长数对链的第一个数对时，最优的选择是挑选第二个数字最小的，这样能给挑选后续的数对留下更多的空间。挑完第一个数对后，要挑第二个数对时，也是按照相同的思路，是在剩下的数对中，第一个数字满足题意的条件下，挑选第二个数字最小的。

解题步骤

1. 将输入按照第二个数字排序
2. 遍历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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度：O(nlogn),排序时间复杂度
空间复杂度：O(logn),排序空间复杂度

动态规划

解题思路

1. 定义 dp[i] 为以pairs[i] 为结尾的最长数对链的长度。
2. 计算 dp[i] 时，可以先找出所有的满足pairs[i][0]>pairs[j][1] 的 j，并求出最大的dp[j]，dp[i] 的值即可赋为这个最大值加一。
3. 注意：这种动态规划的思路要求计算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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

时间复杂度：O(n^2)
空间复杂度：O(n)