300. 最长递增子序列

难度：🟡 Medium | 标签：动归、二分 | 状态：⬜ LeetCode 链接

思路

朴素 DP：dp[i] = max(dp[j] + 1) for j < i and nums[j] < nums[i]，O(n²)。

最优 O(n log n)：维护 tails[]——长度为 k+1 的所有递增子序列的最小尾。 对每个 x：二分找第一个 >= x 的位置替换，若无则 append。

注意：tails 数组长度即 LIS 长度，但内容不是真的 LIS。

代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> tails;
        for (int x : nums) {
            auto it = lower_bound(tails.begin(), tails.end(), x);
            if (it == tails.end()) tails.push_back(x);
            else *it = x;
        }
        return tails.size();
    }
};

复杂度

• 时间 O(n log n)，空间 O(n)

易错 / 回顾

• lower_bound 是严格递增；非严格（673）用 upper_bound
• tails 不是 LIS 本身——别被误导
• 输出 LIS 本身需另存前驱链