LeetCode 300. 最长递增子序列
题目描述
题意分析
从数组中按原先顺序选出若干元素，使后一个元素严格大于前一个元素，返回能选出的最大个数。子序列允许跳过元素，但不能改变相对顺序，因此不能先给原数组排序。
“严格递增”意味着相等元素不能接在彼此后面。题目只需要最长长度，不要求返回具体的子序列；这使我们可以只保存有利于继续扩展的候选状态，避免枚举所有选法。
解法：贪心 + 二分查找
核心思路
[!blue]
从左到右处理元素。对于长度相同的两条递增子序列，结尾越小，后面能接上的值就越多：能接在较大结尾后面的元素，一定也能接在较小结尾后面。因此每种长度只需保留最小结尾，不必保存这一长度的所有候选。
用
tails[i]表示已处理前缀中，长度为i + 1的递增子序列能取得的最小结尾，用size表示目前最长的长度。只有[0, size)是有效状态，每个尾值都对应一条真实存在的子序列，但不同位置可能对应不同的选法。这些最小尾值严格递增。取一条长度为
i + 2、结尾达到tails[i + 1]的子序列，它的前i + 1个元素也递增，且结尾严格小于最后一个元素；而tails[i]不会比这个前缀的结尾更大，所以必有tails[i] < tails[i + 1]。因此可以对有效尾值进行二分查找。遇到当前元素
num，找到第一个满足tails[p] >= num的位置p。如果p > 0，就有tails[p - 1] < num，说明此前存在一条长度为p的序列能接上当前元素，形成长度为p + 1的序列；如果p = 0，当前元素自己就构成长度为1的序列。为什么只能更新这个长度？若
p < size，长度为p + 1的所有已有序列，其结尾都不小于最小值tails[p]，也就都不小于num，无法再接上它。当前元素不能产生更长的序列，却能把长度为p + 1的最小结尾降低到num。如果没有找到这样的尾值，即p = size，则当前元素能接在已有最长序列后面，使长度增加一。因此每轮只需写入
tails[p] = num，并仅在p == size时增加size。相等值会替换已有位置而不会延长，正好符合严格递增的要求。所有状态都由之前已经存在的序列加上当前元素产生，所以有效长度不会虚增；保留最小结尾又不会排除更好的后续扩展，最终size就是答案。
解题步骤
- 分配长度为
n的tails，初始化有效长度size = 0。- 按原数组顺序遍历每个
num，在有效范围[0, size)中查找第一个大于等于它的位置。- 二分时，若
tails[mid] < num，目标位置在右侧，令left = mid + 1；否则当前位置仍可能是答案，令right = mid。- 当
left == right，写入tails[left] = num；如果left == size，说明形成了更长的序列，再将size加一。- 全部处理完毕后返回
size，不直接把tails当成答案序列。
代码实现
class Solution {
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int size = 0;
for (int num : nums) {
// 只搜索有效尾值范围，后面的预分配位置不参与二分。
int left = 0;
int right = size;
while (left < right) {
int mid = left + (right - left) / 2;
if (tails[mid] < num) {
left = mid + 1;
} else {
right = mid;
}
}
// 替换同长度的结尾；只有越过末尾时才增加长度。
tails[left] = num;
if (left == size) {
size++;
}
}
return size;
}
}
func lengthOfLIS(nums []int) int {
tails := make([]int, len(nums))
size := 0
for _, num := range nums {
// 只搜索有效尾值范围，后面的预分配位置不参与二分。
left, right := 0, size
for left < right {
mid := left + (right-left)/2
if tails[mid] < num {
left = mid + 1
} else {
right = mid
}
}
// 替换同长度的结尾；只有越过末尾时才增加长度。
tails[left] = num
if left == size {
size++
}
}
return size
}
复杂度分析
- 时间复杂度：$O(n \log n)$，每个元素执行一次二分查找。
- 空间复杂度：$O(n)$，用于保存
tails。
关键点总结
[!green]
tails[i]表示长度为i + 1的递增子序列的最小结尾。- 查找第一个
>= num的位置，才能保证“严格递增”。- 替换结尾不会改变已有长度，只会增加后续扩展的机会。
tails不一定是原数组中的真实子序列，答案只取其有效长度。
易错点总结
[!yellow]
- 将二分条件写成查找第一个
> num，会把重复元素错误地计入答案。- 在整个
tails数组上二分，而不是只搜索有效区间[0, size)。- 替换已有结尾时误增
size；只有left == size时长度才增加。- 把子序列当成连续子数组，或先排序后再求长度。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 354. 俄罗斯套娃信封问题 | 困难 | 先按宽排序并处理等宽项后，可把二维严格嵌套转成高度的LIS。 |
| 673. 最长递增子序列的个数 | 中等 | 在最长长度状态之外增加方案数，本题只要求一个长度。 |
| 补充题 138. 字典序最小的最长递增子序列 | 中等 | 都先求最长递增子序列长度；补充题还需在可行选择中确定字典序最小的序列。 |