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`` 不是某一条必须真实存在的完整子序列,只是各长度的最小尾值摘要;题目只要求长度, 因此不需要保存前驱下标或恢复具体路径。