最长递增子序列

给你一个整数数组 nums，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除或不删除数组中的元素，并且不改变其余元素的顺序。

例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4

进阶：

你能将算法的时间复杂度降低到 O(n log n) 吗？

解法一（动态规划）：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);

        int ans = 1;

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[j] < nums[i])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }

            ans = max(ans, dp[i]);
        }

        return ans;
    }
};

解法二（贪心 + 二分查找）：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> tails;

        for (int num : nums)
        {
            auto it = lower_bound(tails.begin(), tails.end(), num);

            if (it == tails.end())
            {
                tails.push_back(num);
            }
            else
            {
                *it = num;
            }
        }

        return tails.size();
    }
};

核心思想

这题要求的是最长严格递增子序列的长度。

注意，子序列不要求连续，只要求保持原数组中的相对顺序。

最直接的想法是：

• 枚举每个位置 i 作为递增子序列的结尾
• 再看它前面哪些位置 j 可以接到它前面

如果 nums[j] < nums[i]，那么以 nums[j] 结尾的递增子序列后面可以接上 nums[i]。

这就是动态规划。

进阶要求 O(n log n)，需要换一个角度：

对于相同长度的递增子序列，结尾元素越小，后面越容易继续接更大的数。

所以我们维护一个数组 tails：

• tails[k] 表示长度为 k + 1 的递增子序列中，最小的结尾元素
• tails 本身保持递增
• 每来一个新数，用二分查找找到它应该更新的位置

最后 tails 的长度就是最长递增子序列的长度。

状态定义

解法一中定义：

dp[i] 表示以 nums[i] 作为最后一个元素的最长严格递增子序列长度。

注意这里必须强调“以 nums[i] 结尾”。

因为如果只定义成“前 i 个元素中的最长递增子序列长度”，就很难判断 nums[i] 能不能接在某个序列后面。

题目要求的是整个数组的最长递增子序列长度，所以答案是：

max(dp[i])

其中 0 <= i < n。

递推公式推导

考虑以 nums[i] 结尾的递增子序列。

如果它的长度大于 1，那么它的倒数第二个元素一定来自某个位置 j，并且：

j < i
nums[j] < nums[i]

此时可以把 nums[i] 接在以 nums[j] 结尾的递增子序列后面。

长度变成：

dp[j] + 1

所以要枚举所有满足条件的 j，取最大值：

dp[i] = max(dp[i], dp[j] + 1)

完整条件是：

if (nums[j] < nums[i])
{
    dp[i] = max(dp[i], dp[j] + 1);
}

如果没有任何 j 可以接在 nums[i] 前面，那么 nums[i] 自己也能形成一个长度为 1 的递增子序列。

所以初始值是：

dp[i] = 1

边界情况

数组长度至少为 1。

每个单独的元素都可以构成长度为 1 的严格递增子序列。

所以：

vector<int> dp(n, 1);

如果数组中所有元素都相等，例如：

nums = [7,7,7,7,7,7,7]

因为题目要求严格递增，条件必须是：

nums[j] < nums[i]

相等的元素不能接在一起。

所以答案是 1。

贪心数组 tails 的含义

解法二中维护数组 tails。

它的含义是：

tails[i] 表示长度为 i + 1 的递增子序列中，最小的结尾元素。

例如：

tails = [2, 3, 7]

表示：

• 长度为 1 的递增子序列，最小结尾可以是 2
• 长度为 2 的递增子序列，最小结尾可以是 3
• 长度为 3 的递增子序列，最小结尾可以是 7

这里 tails 不一定是真实的某一个子序列。

它更像是一个记录表，用来保存“每种长度下最有潜力的结尾”。

结尾越小，后面越容易接上新的大数。

为什么使用 lower_bound

对于当前数字 num，在 tails 中找第一个大于等于 num 的位置。

也就是：

auto it = lower_bound(tails.begin(), tails.end(), num);

如果找不到，说明 num 比所有结尾都大，可以接在最长序列后面：

tails.push_back(num);

如果找到了，就用 num 替换这个位置：

*it = num;

这个替换不会让当前已经得到的最长长度变短。

它只是让某个长度的递增子序列结尾变得更小，从而更有利于后续扩展。

因为题目要求严格递增，所以遇到相等元素时不能扩展长度。

使用 lower_bound 找到第一个 >= num 的位置，可以保证相等元素只会替换，不会新增长度。

为什么 tails 一直是递增的

tails[i] 表示长度为 i + 1 的递增子序列的最小结尾。

对于更长的递增子序列，它的结尾一定要大于前面某个较短递增子序列的结尾。

所以整体上：

tails[0] < tails[1] < tails[2] < ...

当新数字 num 来时，我们用二分找到第一个 >= num 的位置并替换。

替换后：

• 它左边的元素都小于 num
• 它右边的元素仍然大于等于原来的值，也大于 num

因此 tails 的递增性质不会被破坏。

正因为 tails 有序，才能用二分查找把每次更新降到 O(log n)。

正确性证明

我们证明：两个解法返回的结果都满足题意。

结论 1：动态规划中，dp[i] 正确表示以 nums[i] 结尾的最长严格递增子序列长度

每个元素本身都可以构成长度为 1 的递增子序列，所以初始化 dp[i] = 1 正确。

对于位置 i，如果某个位置 j 满足：

j < i
nums[j] < nums[i]

那么以 nums[j] 结尾的任意严格递增子序列，都可以接上 nums[i]。

所以候选长度是：

dp[j] + 1

枚举所有满足条件的 j 并取最大值，就不会漏掉任何以 nums[i] 结尾的合法递增子序列。

同时，只有在 nums[j] < nums[i] 时才转移，所以不会加入不严格递增的序列。

因此 dp[i] 的含义正确。

结论 2：动态规划返回 max(dp[i]) 是整个数组的最长递增子序列长度

任意一个非空递增子序列，一定有一个最后元素。

假设它最后一个元素的位置是 i，那么它就是一个以 nums[i] 结尾的递增子序列。

它的长度一定不会超过 dp[i]。

所以整个数组的最长递增子序列长度，就是所有 dp[i] 中的最大值。

结论 3：贪心解法中，tails[i] 始终是长度为 i + 1 的递增子序列的最小可能结尾

初始时 tails 为空，结论显然成立。

处理一个新数字 num 时，有两种情况。

如果 num 比 tails 中所有元素都大，那么它可以接在当前最长递增子序列后面，形成更长的递增子序列。

所以把它加入 tails 末尾是正确的。

如果 num 替换了第一个大于等于它的位置 pos，说明：

• pos 左边的结尾都小于 num
• 因此 num 可以接在长度为 pos 的递增子序列后面
• 替换后，长度为 pos + 1 的递增子序列结尾变得更小或相等

这样不会破坏已有长度，只会让后续扩展更容易。

所以 tails 的含义始终成立。

结论 4：贪心解法中，tails.size() 等于最长递增子序列长度

每当 tails 增加一个元素，就说明当前数字可以接在已有最长递增子序列后面，形成更长的严格递增子序列。

因此 tails.size() 不会超过真实的最长递增子序列长度。

另一方面，tails 中每一个位置都对应某个长度的递增子序列的最小结尾。

所以如果 tails.size() = k，就说明至少存在一个长度为 k 的严格递增子序列。

因此 tails.size() 也不会小于真实答案。

两边合起来可知，tails.size() 就是真实的最长递增子序列长度。

得出结论

由结论 1 和结论 2 可知，动态规划解法正确。

由结论 3 和结论 4 可知，贪心加二分解法正确。

因此两个解法都能返回最长严格递增子序列的长度。

举例理解

以：

nums = [10,9,2,5,3,7,101,18]

为例，看解法二的 tails 变化。

最终 tails 的长度是 4。

所以最长严格递增子序列的长度是：

4

注意最终的 tails = [2,3,7,18] 正好也是一个合法子序列。

但在一般情况下，tails 不一定对应原数组中的某个真实子序列。

它只保证长度正确。

复杂度分析

解法一

外层枚举每个位置 i，内层枚举它前面的所有位置 j。

• 时间复杂度：O(n^2)
• 空间复杂度：O(n)

解法二

每个元素处理一次。

每次在 tails 中进行二分查找，复杂度是 O(log n)。

• 时间复杂度：O(n log n)
• 空间复杂度：O(n)

解法二满足进阶要求，是更推荐的做法。