最长递增子序列 - Stellar Observer Protocol

639 字

3 分钟

最长递增子序列

2025-08-16

Algorithms

数组

/

二分查找

/

动态规划

题目描述#

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

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

解题思路#

动态规划：
- 定义 dp[i] 表示以 nums[i] 结尾的 LIS 长度
- 状态转移：遍历 j=0→i-1，若 nums[i]>nums[j]，则 dp[i] = max(dp[i], dp[j]+1)
- 结果取 max(dp)
贪心+二分优化：
- 维护有序数组 tails，tails[k] 表示长度为 k+1 的 LIS 的最小结尾数
- 遍历时二分查找插入位置：替换首个 ≥ nums[i] 的元素
- tails 长度即为 LIS 长度

关键洞察#

贪心策略有效性：
- 让上升序列尽可能慢地增长
- 小元素替换大元素为未来留空间
tails 数组特性：
- 严格递增（可二分搜索）
- 长度 = LIS 长度
二分查找作用：
- 快速定位元素插入位置
- 保持 tails 有序性
结尾元素重要性：
- 相同长度的 LIS 只需记录最小结尾值
- 避免维护完整序列

复杂度分析#

方法	时间复杂度	空间复杂度	适用场景
动态规划	O(n²)	O(n)	小规模数据
贪心+二分	O(n log n)	O(n)	最优解（推荐）

代码实现#

二分法+贪心

1
/**
2
 * @param {number[]} nums
3
 * @return {number}
4
 */
5
var lengthOfLIS = function (nums) {
6
    const tails = [];
7
    for (let num of nums) {
8
        let left = 0, right = tails.length;
9
        while (left < right) {
10
            let mid = (left + right) >> 1;
11
            if (tails[mid] < num) left = mid + 1;
12
            else right = mid;
13
        }
14
        tails[left] = num;
15
    }
16
    return tails.length;
17
};

动态规划法

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