LIS 最長遞增子序列：Java O(n log n) 最優解法與完整代碼

問題定義

給定一個整數數組 nums，找出最長嚴格遞增子序列的長度。子序列不要求連續，但順序不能變。

例如：[10,9,2,5,3,7,101,18] → LIS 為 [2,3,7,101]，長度 = 4。

算法演進：從 O(n²) 到 O(n log n)

1. 動態規劃 O(n²) —— 適合面試講解思路

• dp[i] 表示以 nums[i] 結尾的 LIS 長度。
• 狀態轉移：dp[i] = max(dp[j]) + 1，其中 j < i 且 nums[j] < nums[i]。
• 時間 O(n²)，空間 O(n)。

public int lengthOfLIS_DP(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int max = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        max = Math.max(max, dp[i]);
    }
    return max;
}

2. 貪心 + 二分查找 O(n log n) —— 生產環境首選

核心思想：維護一個數組 tails，其中 tails[len] 存儲長度為 len+1 的所有遞增子序列中「最小的結尾值」。遍歷數組，對每個 x：

• 若 x > tails[last]，直接擴展長度。
• 否則在 tails 中二分查找第一個 ≥ x 的位置並替換，保證 tails 單調遞增。

最終 tails 的有效長度即為 LIS 長度。

public int lengthOfLIS_Optimal(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int[] tails = new int[nums.length];
    int size = 0;
    for (int x : nums) {
        int l = 0, r = size;
        while (l < r) {
            int m = (l + r) >>> 1;
            if (tails[m] < x) l = m + 1;
            else r = m;
        }
        tails[l] = x;
        if (l == size) size++;
    }
    return size;
}

3. 進階：輸出具體的一條 LIS 序列（而非僅長度）

需額外維護 prev[] 指針與 tailsIdx[] 記錄每個長度對應的數組下標，最後回溯重建。

public List getLIS(int[] nums) {
    int n = nums.length;
    int[] tails = new int[n];
    int[] tailsIdx = new int[n];
    int[] prev = new int[n];
    Arrays.fill(prev, -1);
    int size = 0;

    for (int i = 0; i < n; i++) {
        int x = nums[i];
        int l = 0, r = size;
        while (l < r) {
            int m = (l + r) >>> 1;
            if (tails[m] < x) l = m + 1;
            else r = m;
        }
        tails[l] = x;
        tailsIdx[l] = i;
        if (l > 0) prev[i] = tailsIdx[l - 1];
        if (l == size) size++;
    }

    // 回溯構建序列
    List lis = new ArrayList<>();
    for (int k = tailsIdx[size - 1]; k != -1; k = prev[k]) {
        lis.add(nums[k]);
    }
    Collections.reverse(lis);
    return lis;
}

測試用例

@Test
public void testLIS() {
    int[] a1 = {10,9,2,5,3,7,101,18};
    assertEquals(4, lengthOfLIS_Optimal(a1));
    assertEquals(List.of(2,3,7,101), getLIS(a1));

    int[] a2 = {0,1,0,3,2,3};
    assertEquals(4, lengthOfLIS_Optimal(a2));
    assertEquals(List.of(0,1,2,3), getLIS(a2));

    int[] a3 = {7,7,7,7,7};
    assertEquals(1, lengthOfLIS_Optimal(a3));
    assertEquals(List.of(7), getLIS(a3));
}

複雜度對比總結

掌握 tails 數組的物理意義與二分查找邊界條件，是寫出正確 O(n log n) LIS 代碼的關鍵。建議在 LeetCode 300 題反復練習直到肌肉記憶。