LeetCode 646. 最长数对链

Categories:

题目描述
思路分析
1. 解法一：贪心（推荐）
2. 解法二：动态规划
相似题目

题目描述

✅ 646. 最长数对链

思路分析

解法一：贪心（推荐）

核心思路：

按照每个数对的第二个数（右端点）升序排序

贪心地选择右端点尽可能小的数对，使得后续数对有更多机会拼接

遍历数对，若当前数对左端点大于上一个选中数对的右端点，则选择该数对，链长度加一

复杂度分析：

时间复杂度：O(n log n)，其中 n 为数对个数，排序耗时 O(n log n)

空间复杂度：O(log n)，排序递归栈空间

class Solution {
    public int findLongestChain(int[][] pairs) {
        // 按右端点升序排序
        Arrays.sort(pairs, (a, b) -> a[1] - b[1]);

        int count = 0;
        int curEnd = Integer.MIN_VALUE;

        for (int[] pair : pairs) {
            // 当前数对左端点严格大于上一个右端点，可以拼接
            if (pair[0] > curEnd) {
                count++;
                curEnd = pair[1];
            }
        }

        return count;
    }
}

func findLongestChain(pairs [][]int) int {
    // 按右端点升序排序
    sort.Slice(pairs, func(i, j int) bool {
        return pairs[i][1] < pairs[j][1]
    })

    count := 0
    curEnd := math.MinInt32

    for _, pair := range pairs {
        // 当前数对左端点严格大于上一个右端点，可以拼接
        if pair[0] > curEnd {
            count++
            curEnd = pair[1]
        }
    }

    return count
}

解法二：动态规划

核心思路：

按左端点排序，定义 dp[i] 为以第 i 个数对结尾的最长链长度

对每个数对 i，枚举所有 j < i，若 pairs[j][1] < pairs[i][0]，则 dp[i] = max(dp[i], dp[j] + 1)

答案为 max(dp)

复杂度分析：

时间复杂度：O(n²)，其中 n 为数对个数，双重循环

空间复杂度：O(n)，dp 数组

class Solution {
    public int findLongestChain(int[][] pairs) {
        // 按左端点升序排序
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);

        int n = pairs.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        int ans = 1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // 数对 j 的右端点严格小于数对 i 的左端点
                if (pairs[j][1] < pairs[i][0]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }

        return ans;
    }
}

func findLongestChain(pairs [][]int) int {
    // 按左端点升序排序
    sort.Slice(pairs, func(i, j int) bool {
        return pairs[i][0] < pairs[j][0]
    })

    n := len(pairs)
    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }

    ans := 1

    for i := 1; i < n; i++ {
        for j := 0; j < i; j++ {
            // 数对 j 的右端点严格小于数对 i 的左端点
            if pairs[j][1] < pairs[i][0] {
                if dp[j]+1 > dp[i] {
                    dp[i] = dp[j] + 1
                }
            }
        }
        if dp[i] > ans {
            ans = dp[i]
        }
    }

    return ans
}

相似题目

题目	难度	考察点
300. 最长递增子序列	中等	动态规划/贪心
435. 无重叠区间	中等	贪心/区间调度
452. 用最少数量的箭引爆气球	中等	贪心/区间
354. 俄罗斯套娃信封问题	困难	动态规划/贪心
56. 合并区间	中等	排序/区间合并
1235. 规划兼职工作	困难	动态规划/二分

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/34661161