0300. Longest Increasing Subsequence
====================================
题目信息
--------
:题号: 0300
:难度: Medium
:主题: 数组、子序列、严格递增、长度优化
:原题: `LeetCode 0300 `_
:重点: 子序列可以跳过元素但不能改变原顺序、相等值不能延长、只返回最大长度
题目重述
--------
给定整数数组 ``nums``,返回其中最长严格递增子序列的长度。子序列由原数组删除任意数量的元素后得到,保留下来的元素必须继续保持原有下标顺序,但不要求在原数组中连续。
严格递增要求序列中每个后继元素都大于前一个元素,因此相等值不能作为一次增长。数组长度位于 ``[1, 2500]``,每个元素位于 ``[-10^4, 10^4]``。题目只要求返回长度,不需要恢复具体子序列;当存在多个同样长的答案时,它们都对应同一个返回值。进阶问题要求把时间复杂度优化到 ``O(n log n)``。
自建示例
--------
最优子序列需要跳过部分元素:
.. code-block:: text
输入:nums = [3, 1, 2, 5, 4, 7]
输出:4
解释:例如 [1,2,4,7] 是长度为 4 的严格递增子序列;元素 4 虽位于 5 之后,仍可跳过 5 保持原下标顺序。
全部元素相等:
.. code-block:: text
输入: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++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int lengthOfLIS(std::vector& nums) {
std::vector 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(tails.size());
}
};
代码分析
--------
每个元素在 ``tails`` 上做一次二分查找,时间复杂度为 ``O(n log n)``,额外空间为 ``O(n)``。
``tails`` 不是某一条必须真实存在的完整子序列,只是各长度的最小尾值摘要;题目只要求长度,
因此不需要保存前驱下标或恢复具体路径。