646. 最长数对链

leetcode 646. 最长数对链

题目：646. 最长数对链

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

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

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

示例:

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

注意:

给出数对的个数在 [1, 1000] 范围内。

方法一：贪心

思路：贪心，事先对pairs数对数组中数对的第二个数进行从小到大排序。遍历pairs，将排序后的第一个数对作为数对链的第一个数对，用ans记录当前数对链的长度，用current数组保存当前数对链中最后一个对数，继续遍历，通过比较遍历数对的第一个数是否大于数对链末尾数对中的第二个数，从而判断该遍历数对是否可以链接在数对链上，可以的话更新current、ans。由于对所有数对进行了排序，所以可以确保每次遍历数对都是在当前的最优的链接数对链的数对。

运行数据：执行用时：11 ms，内存消耗：39.4 MB

复杂度分析：

• 时间复杂度：O(n * log(n))，n为pairs的长度，主要是排序的时间复杂度。
• 空间复杂度：O(n)，n为pairs的长度，主要是排序的辅助空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// LeetCode指定调用方法 
public int findLongestChain(int[][] pairs) {
		
    Arrays.sort(pairs, (a, b) -> (a[1] - b[1]));

    int ans = 0;
    int[] current = null;
    for (int[] is : pairs) {
        if (current == null) {
            current = is;
            ans = 1;
        } else {
            if (is[0] > current[1]) {
                current = is;
                ans++;
            }
        }

    }
    return ans;
}

方法二：动态规划

思路：动态规划，状态转移方程为：dp[i] = max(dp[i], dp[j] + 1);（pairs[i][0] > pairs[j][1]）。dp[i]表示以pairs[i]结尾的最长数对链长度。

运行数据：执行用时：11 ms，内存消耗：39.4 MB

复杂度分析：

• 时间复杂度：O(n^2)，n为pairs的长度，主要是动态规划的两层循环。
• 空间复杂度：O(n)，n为pairs的长度，主要是dp数组消耗的空间。

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

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

学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。

才疏学浅，若有错误或不当之处，可批评指正，还请见谅！