算法 - 最长递增子序列 (LIS)

Posted on

1. 题目

给你一个整数数组 nums，取出其中严格递增的最长子序列，返回其长度。子序列不要求连续，但要保持相对顺序。

示例:

1
2
3
4
5
输入: nums = [10, 9, 2, 5, 3, 7, 101, 18]
输出: 4  （最长递增子序列为 [2, 3, 7, 101]）

输入: nums = [0, 1, 0, 3, 2, 3]
输出: 4  （[0, 1, 2, 3]）

2. 解题思路

2.1 动态规划 O(n²)

定义 dp[i] = 以 nums[i] 结尾的最长递增子序列长度。

对每个 i，回看所有 j < i：若 nums[j] < nums[i]，则可以把 nums[i] 接在以 j 结尾的序列后面：

1
dp[i] = max(dp[j] + 1)  对所有 nums[j] < nums[i]

初始每个 dp[i] = 1（自己单独成列）。答案是 max(dp)，注意不是 dp[n-1]（结尾不一定是全局最长）。

2.2 贪心 + 二分 O(n log n)（最优）

维护数组 tails：tails[k] 表示「长度为 k+1 的递增子序列的最小可能结尾」。直觉：同样长度下，结尾越小越容易再接更大的数，越有潜力。

遍历 nums 中每个 x：

  • 用二分在 tails 中找第一个 >= x 的位置：
    • 找到 → 用 x 替换它（让这个长度的结尾更小）。
    • 没找到（x 比所有都大）→ push 到末尾，LIS 长度 +1。
  • tails 的长度即为答案。

注意：tails 本身不是某个真实的子序列，只是长度正确；不要试图从中还原路径。

  • 时间复杂度：O(n log n)；空间复杂度：O(n)。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 2.1 DP：O(n²)
function lengthOfLIS(nums: number[]): number {
    const n = nums.length;
    const dp = new Array(n).fill(1);
    let ans = 1;

    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        ans = Math.max(ans, dp[i]);
    }
    return ans;
}

// 2.2 贪心 + 二分：O(n log n)
function lengthOfLISNLogN(nums: number[]): number {
    const tails: number[] = [];

    for (const x of nums) {
        // 二分找第一个 >= x 的下标（lowerBound）
        let lo = 0;
        let hi = tails.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (tails[mid] < x) lo = mid + 1;
            else hi = mid;
        }

        if (lo === tails.length) tails.push(x); // x 最大，延长
        else tails[lo] = x;                       // 替换，压小结尾
    }

    return tails.length;
}

console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 4
console.log(lengthOfLISNLogN([0, 1, 0, 3, 2, 3]));       // 4

4. 面试延伸

  • 非严格递增（允许相等）：把二分的 lowerBound 换成 upperBound（找第一个 > x）。一个字符之差，常考。
  • 俄罗斯套娃信封（354）：先按宽升序、宽相同按高降序排序，再对高求 LIS，是 LIS 的二维包装。
  • 最长递增子序列的个数（673）：在 DP 里再维护一个 count[] 数组。
  • 要求输出具体子序列：只能用 O(n²) DP + parent[] 回溯，贪心二分法无法直接还原（可另存下标）。
  • 面试写二分要能讲清 lo 的含义（第一个 >= x），否则容易 off-by-one。

难度：中等 | LeetCode 300 题 | DP + 二分双考点