leetcode646. 最长数对链(java)

题目描述

难度 - 中等
leetcode646. 最长数对链(java)

给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < righti 。
现在，我们定义一种 跟随 关系，当且仅当 b < c 时，数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链 。
找出并返回能够形成的 最长数对链的长度 。
你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

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

示例 2：
输入：pairs = [[1,2],[7,8],[4,5]]
输出：3
解释：最长的数对链是 [1,2] -> [4,5] -> [7,8] 。

提示：
n == pairs.length
1 <= n <= 1000
-1000 <= lefti < righti <= 1000

贪心

要挑选最长数对链的第一个数对时，最优的选择是挑选第二个数字最小的，这样能给挑选后续的数对留下更多的空间。挑完第一个数对后，要挑第二个数对时，也是按照相同的思路，是在剩下的数对中，第一个数字满足题意的条件下，挑选第二个数字最小的。按照这样的思路，可以先将输入按照第二个数字排序，然后不停地判断第一个数字是否能满足大于前一个数对的第二个数字即可。

代码演示：

    public int findLongestChain(int[][] pairs) {
          Arrays.sort(pairs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        int ans = 0;
        int cur = Integer.MIN_VALUE;
        for(int[] p : pairs){
            if(cur < p[0]){
                ans++;
                cur = p[1];
            }
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

解法二 动态规划 dp

起始先将 pairs 根据第一维排升序（或直接双关键字排升序）。
考虑定义 f[i] 为以 pairs[i] 为结尾的最长数对链长度，所有 f[i] 中的最大值为答案。
不失一般性考虑 f[i] 该如何转移：不难发现 f[i]为所有满足「下标范围在 [0,i−1]，且 pairs[j][1]

但实际上，我们只需要从 j=i−1 开始往回找，找到第一个满足 pairs[j][1]

容易证明该做法的正确性：假设贪心解（该做法）找到的位置 jjj 不是最优位置，即存在比 j 更小的合法下标 j′ 满足 f[j′]>f[j]]。根据我们的排序规则必然有 pairs[j′][0]<=pairs[j][0]的性质，则可知 pairs[j] 必然可以代替 pairs[j′] 接在原本以 pairs[j′]为结尾的最优数链上（最优数链长度不变，结果不会变差），则至少有 f[j′]=f[j]。

代码演示：

  public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs,(a,b) -> {
            return a[0] - b[0];
        });
        int ans = 1;
        int n = pairs.length;
        int[] dp = new int[n];
        for(int i = 0; i < n;i++){
            dp[i] = 1;
            for(int j = i - 1; j >= 0 && dp[i] == 1;j--){
                if(pairs[j][1] < pairs[i][0]){
                    dp[i] = dp[j] + 1;
                }
            }
            ans = Math.max(ans,dp[i]);

        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19