0300. Longest Increasing Subsequence¶
题目信息¶
- 题号:
0300
- 难度:
Medium
- 主题:
数组、子序列、严格递增、长度优化
- 原题:
- 重点:
子序列可以跳过元素但不能改变原顺序、相等值不能延长、只返回最大长度
题目重述¶
给定整数数组 nums,返回其中最长严格递增子序列的长度。子序列由原数组删除任意数量的元素后得到,保留下来的元素必须继续保持原有下标顺序,但不要求在原数组中连续。
严格递增要求序列中每个后继元素都大于前一个元素,因此相等值不能作为一次增长。数组长度位于 [1, 2500],每个元素位于 [-10^4, 10^4]。题目只要求返回长度,不需要恢复具体子序列;当存在多个同样长的答案时,它们都对应同一个返回值。进阶问题要求把时间复杂度优化到 O(n log n)。
自建示例¶
最优子序列需要跳过部分元素:
输入:nums = [3, 1, 2, 5, 4, 7]
输出:4
解释:例如 [1,2,4,7] 是长度为 4 的严格递增子序列;元素 4 虽位于 5 之后,仍可跳过 5 保持原下标顺序。
全部元素相等:
输入:nums = [2, 2, 2]
输出:1
解释:严格递增不允许相邻选中值相等,所以任何合法递增子序列最多只包含一个元素。
维护每种长度的最小尾值¶
tails[len-1] 表示目前找到的长度为 len 的严格递增子序列中,可能达到的最小尾值。
处理新值 x 时,在 tails 中寻找第一个不小于 x 的位置:
若该位置存在,用
x替换它,得到同样长度但更有希望继续延长的尾值;若所有尾值都小于
x,把x追加,说明最长长度增加 1。
必须使用 lower_bound``(第一个 ``>=x),因为题目要求严格递增;若使用 upper_bound,
相等值会被错误地当作可以延长序列。
正确性说明¶
对每个长度 len,较小的尾值不会减少未来可接上的元素集合,因此用 x 替换第一个不小于它的尾值不会丢失任何
长度 len 的可能性。tails 始终严格递增:替换位置左侧都更小,右侧原本更大;
只有当 x 大于全部尾值时才新增长度。若最终长度为 L,它对应实际构造过的长度 L 子序列,
而任何更长长度都没有出现,所以 L 正是最长递增子序列长度。
C++ 实现¶
class Solution {
public:
int lengthOfLIS(std::vector<int>& nums) {
std::vector<int> tails;
for (int value : nums) {
auto position = std::lower_bound(
tails.begin(), tails.end(), value);
if (position == tails.end()) tails.push_back(value);
else *position = value;
}
return static_cast<int>(tails.size());
}
};
代码分析¶
每个元素在 tails 上做一次二分查找,时间复杂度为 O(n log n),额外空间为 O(n)。
tails 不是某一条必须真实存在的完整子序列,只是各长度的最小尾值摘要;题目只要求长度,
因此不需要保存前驱下标或恢复具体路径。