0300. Longest Increasing Subsequence

题目信息

题号:

0300

难度:

Medium

主题:

数组、子序列、严格递增、长度优化

原题:

LeetCode 0300

重点:

子序列可以跳过元素但不能改变原顺序、相等值不能延长、只返回最大长度

题目重述

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