algorithms►leetcode

017-最长递增子序列(DP or 贪心+二分)

最长递增子序列（LIS）

最长递增子序列（Longest Increasing Subsequence）是算法中经典的动态规划问题。

问题描述

给定一个无序的整数数组，找到其中最长的严格递增子序列的长度。

示例：

1
2
3
输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的递增子序列是 [2,3,7,101]，长度为4

方法一：动态规划（O(n²)）

解题思路

  1. 创建 dp 数组，dp[i] 表示以 nums[i] 结尾的最长递增子序列长度
  2. 初始时每个元素本身就是一个子序列，所以初始值为 1
  3. 对于每个元素，检查前面所有比它小的元素，更新 dp 值
  4. 最后返回 dp 数组中的最大值

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function lengthOfLIS(nums) {
    if (nums.length === 0) return 0;
    
    const dp = new Array(nums.length).fill(1);
    let maxLen = 1;
    
    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    
    return maxLen;
}

复杂度分析

  • 时间复杂度：O(n²) - 双重循环
  • 空间复杂度：O(n) - dp 数组

方法二：贪心+二分查找（O(nlogn)）

解题思路

  1. 维护一个 tails 数组，tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素
  2. 遍历数组，对于每个数字：
    • 如果它比 tails 最后一个元素大，直接加入数组
    • 否则，用二分查找找到第一个 ≥ 它的元素并替换
  3. tails 的长度就是最长递增子序列的长度

代码实现

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
function lengthOfLIS(nums) {
    const tails = [];
    
    for (const num of nums) {
        let left = 0, right = tails.length;
        
        // 二分查找插入位置
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (tails[mid] < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        if (left === tails.length) {
            tails.push(num);
        } else {
            tails[left] = num;
        }
    }
    
    return tails.length;
}

复杂度分析

  • 时间复杂度：O(nlogn) - 遍历数组 O(n)，每个元素二分查找 O(logn)
  • 空间复杂度：O(n) - tails 数组

两种方法对比

方法 时间复杂度 空间复杂度 适用场景
动态规划 O(n²) O(n) 小规模数据，需要知道具体序列
贪心+二分 O(nlogn) O(n) 大规模数据，只需长度

示例测试

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

进阶：输出具体的最长递增子序列

如果需要输出具体的序列而不仅仅是长度，可以修改动态规划解法：

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
function getLIS(nums) {
    const dp = new Array(nums.length).fill(1);
    const prev = new Array(nums.length).fill(-1);
    let maxIndex = 0;
    
    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
                prev[i] = j;
            }
        }
        if (dp[i] > dp[maxIndex]) {
            maxIndex = i;
        }
    }
    
    const result = [];
    while (maxIndex !== -1) {
        result.unshift(nums[maxIndex]);
        maxIndex = prev[maxIndex];
    }
    
    return result;
}

总结

最长递增子序列问题有两种主要解法：

  1. 动态规划：直观易懂，适合小规模数据和需要输出具体序列的情况
  2. 贪心+二分：效率更高，适合大规模数据但实现稍复杂

最长递增子序列（LIS）贪心+二分法详细图解

贪心+二分法是最优的LIS解法，时间复杂度O(nlogn)。下面我用详细的步骤和图解来解释这个算法。

算法核心思想

维护一个tails数组，其中tails[i]表示长度为i+1的所有递增子序列的最小末尾元素。

示例数组

nums = [10, 9, 2, 5, 3, 7, 101, 18]

详细步骤图解

初始状态

tails = [] (空数组)

处理每个元素：

  1. i=0, num=10

    • tails为空，直接加入
    • tails = [10]
    • 解释：长度为1的子序列最小末尾是10

  2. i=1, num=9

    • 二分查找9在tails中的位置
    • tails = [10]，找到第一个≥9的是10
    • 替换10→9
    • tails = [9]
    • 解释：长度为1的子序列最小末尾现在是9

  3. i=2, num=2

    • tails = [9]，找到第一个≥2的是9
    • 替换9→2
    • tails = [2]
    • 解释：长度为1的子序列最小末尾现在是2

  4. i=3, num=5

    • tails = [2]，5>2，可以扩展
    • 加入5
    • tails = [2, 5]
    • 解释：
      • 长度为1的最小末尾：2
      • 长度为2的最小末尾：5

  5. i=4, num=3

    • tails = [2,5]，二分查找3
    • 找到第一个≥3的是5
    • 替换5→3
    • tails = [2,3]
    • 解释：
      • 长度为1的最小末尾：2
      • 长度为2的最小末尾：3

  6. i=5, num=7

    • tails = [2,3]，7>3，可以扩展
    • 加入7
    • tails = [2,3,7]
    • 解释：
      • 长度1：2
      • 长度2：3
      • 长度3：7

  7. i=6, num=101

    • tails = [2,3,7]，101>7，可以扩展
    • 加入101
    • tails = [2,3,7,101]
    • 解释：
      • 长度1：2
      • 长度2：3
      • 长度3：7
      • 长度4：101

  8. i=7, num=18

    • tails = [2,3,7,101]，二分查找18
    • 找到第一个≥18的是101
    • 替换101→18
    • tails = [2,3,7,18]
    • 解释：
      • 长度1：2
      • 长度2：3
      • 长度3：7
      • 长度4：18 (比101更小)

完整过程表格

步骤 当前数字 tails数组变化 操作说明
1 10 [10] 直接加入
2 9 [9] 替换10→9
3 2 [2] 替换9→2
4 5 [2,5] 5>2，扩展
5 3 [2,3] 替换5→3
6 7 [2,3,7] 7>3，扩展
7 101 [2,3,7,101] 101>7，扩展
8 18 [2,3,7,18] 替换101→18

为什么这样能得到正确结果？

  1. 贪心策略：我们总是希望递增子序列的末尾元素尽可能小，这样后面有更多机会扩展更长的序列
  2. tails数组性质：tails数组一定是严格递增的，这保证了我们可以使用二分查找
  3. 替换不影响长度：当我们替换某个位置的元素时，不会改变当前的最大长度，只是为未来可能的扩展创造了更好的条件

最终结果

tails数组的最终长度是4，因此最长递增子序列的长度为4。

可能的LIS序列：

  • [2,3,7,101]
  • [2,3,7,18]

虽然tails数组不直接给出具体的LIS，但它正确记录了LIS的长度。