最长递增子序列（Longest Increasing Subsequence，LIS）是一个经典的动态规划问题，目标是在给定数组中找到一个最长的严格递增子序列（元素可以不连续）。以下从算法原理到优化实现进行详细解析：
一、问题定义
给定一个无序的整数数组 nums，找到其中最长严格递增子序列的长度。
1
2
3
| 输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，长度为4。
|
二、动态规划解法（基础）
核心思路
- 状态定义：
dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。
- 状态转移：对于每个
i，遍历其前面的所有元素 j（0 ≤ j < i），如果 nums[j] < nums[i]，则 dp[i] = max(dp[i], dp[j] + 1)。
- 初始状态：每个元素自身构成一个长度为1的子序列，故
dp[i] = 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
function lengthOfLIS(nums: number[]){
if(!nums.length) return;
const len = nums.length;
const dp = Array(len).fill(1)
for(let i = 0; i < len; i++){
for(let j = 0; j < i; j++){
if(nums[j] < nums[i]){
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Math.max(...dp)
}
function lengthOfLIS(nums: number[]){
if(!nums.length) return;
const len = nums.length;
const dp = Array(len).fill(1)
const preNode = Array(len).fill(-1);
let maxLen = 1, lastIndex = 0;
for(let i = 0; i < len; i++){
for(let j = 0; j < i; j++){
if(nums[j] < nums[i] && dp[i] <= dp[j] + 1){
dp[i] = dp[j] + 1;
preNode[i] = j;
}
}
if(dp[i]> maxLen){
maxLen = dp[i];
lastIndex = i;
}
}
const res: number[] = [];
while(lastIndex !== -1){
res.push(nums[lastIndex]);
lastIndex = preNode[lastIndex];
}
return res.reverse();
}
|
复杂度分析
- 时间复杂度：$O(n^2)$，需要两层循环。
- 空间复杂度：$O(n)$，用于存储
dp 数组。
三、贪心 + 二分查找（优化解法）
核心思路
- 维护一个数组
tails：其中 tails[k] 表示长度为 k+1 的递增子序列的末尾最小元素。
- 遍历数组：对于每个元素
num，通过二分查找找到其在 tails 中的插入位置：
- 如果
num 大于所有 tails 中的元素，直接添加到末尾，形成更长的子序列。
- 否则，替换第一个大于等于
num 的元素，保持 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| function lengthOfLIS(nums: number[]){
const tails: number[] = []
const len = nums.length
const preNode: number[] = Array(len).fill(-1);
const preIndex: number[] = [];
for(let i = 0; i < len; i++){
let left = 0;
let right = tails.length;
while (left < right){
const mid = Math.floor((left + right) / 2)
if(tails[mid] < nums[i]){
left = mid + 1
}else{
right = mid
}
}
if (left === tails.length){
tails.push(nums[i])
}else{
tails[left] = nums[i]
}
preNode[i] = tails[left-1] ? preIndex[tails[left-1]]:-1
preIndex[nums[i]] = i
}
const lastItem = tails[tails.length-1];
const res = [lastItem];
const index = preIndex[lastItem];
let node = preNode[index];
while(node !== -1){
res.push(nums[node]);
node = preNode[node]
}
return tails.length
}
|
复杂度分析
- 时间复杂度：$O(n \log n)$，每次二分查找耗时 $O(\log n)$。
- 空间复杂度：$O(n)$，主要用于存储
tails 数组。
四、关键差异对比
| 方法 |
时间复杂度 |
空间复杂度 |
适用场景 |
| 动态规划 |
$O(n^2)$ |
$O(n)$ |
数据规模较小（n ≤ 1000） |
| 贪心 + 二分查找 |
$O(n \log n)$ |
$O(n)$ |
数据规模较大（n > 1000） |
五、总结
- 动态规划：适用于小规模数据，代码简单易理解。
- 贪心 + 二分查找：适用于大规模数据，性能更优，但逻辑较复杂。
- 应用场景：涉及最长递增子序列的问题（如版本控制、序列比对等）。
掌握这两种解法，能应对大多数 LIS 相关问题，并可根据数据规模选择最优方案。
