646. 最長數對鍊 : 正常貪心 DP 運用題

​

題目描述

這是 LeetCode 上的 646. 最長數對鍊 ，難度為 中等。

Tag : 「貪心」、「排序」、「二分」、「序列 DP」、「LIS」

給出 ​

​n​

​ 個數對。 在每一個數對中，第一個數字總是比第二個數字小。

現在，我們定義一種跟随關系，當且僅當 ​

​b < c​

​​ 時，數對  才可以跟在 

給定一個數對集合，找出能夠形成的最長數對鍊的長度。你不需要用到所有的數對，你可以以任何順序選擇其中的一些數對來構造。

示例：

輸入：[[1,2], [2,3], [3,4]]

輸出：2

解釋：最長的數對鍊是 [1,2] -> [3,4]      

提示：

• 給出數對的個數在

排序 + 貪心 DP

起始先将 ​

​pairs​

​ 根據第一維排升序（或直接雙關鍵字排升序）。

考慮定義 為以 為結尾的最長數對鍊長度，所有

不失一般性考慮 該如何轉移：不難發現 為所有滿足「下标範圍在 ，且 」條件的

但實際上，我們隻需要從 開始往回找，找到第一個滿足 的位置

容易證明該做法的正确性：假設貪心解（該做法）找到的位置 不是最優位置，即存在比 更小的合法下标 滿足 。根據我們的排序規則必然有 的性質，則可知 必然可以代替 接在原本以 為結尾的最優數鍊上（最優數鍊長度不變，結果不會變差），則至少有 。

代碼：

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

• 時間複雜度：排序的複雜度為；不考慮剪枝效果​​

  ​DP​

  ​​ 複雜度為。整體複雜度為
• 空間複雜度：

排序 + 貪心 DP（優化轉移）

根據上述分析，我們知道對于一個特定的 而言，其所有合法（滿足條件 ）的前驅狀态

根據 ​

​LIS​

​ 問題的貪心解的思路，我們可以額外使用一個數組記錄下特定長度數鍊的最小結尾值，進而實作二分找前驅狀态。

具體的，建立 數組，其中 代表數鍊長度為 時結尾元素的第二維最小值為 。

如此一來，當我們要找 的前驅狀态時，等價于在 數組中找滿足「小于 」的最大下标。同時，我們不再需要顯式維護

不了解 ​

​LIS​

​ 問題的同學可以看前置 🧀 : ​​LCS 問題與 LIS 問題的互相關系，以及 LIS 問題的最優解證明 🎉🎉🎉

代碼：

class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a,b)->a[0]-b[0]);
        int n = pairs.length, ans = 1;
        int[] g = new int[n + 10];
        Arrays.fill(g, 0x3f3f3f3f);
        for (int i = 0; i < n; i++) {
            int l = 1, r = i + 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (g[mid] >= pairs[i][0]) r = mid;
                else l = mid + 1;
            }
            g[r] = Math.min(g[r], pairs[i][1]);
            ans = Math.max(ans, r);
        }
        return      

• 時間複雜度：排序的複雜度為；​​

  ​DP​

  ​​ 複雜度為。整體複雜度為
• 空間複雜度：

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.646​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。