最长递增子序列 图解题解

这道题到底在问什么

nums

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

输出

4，例如 [2,3,7,101]

最优解：一步一步想明白

1. 3每个数选或不选，会产生指数级组合。台阶是 2^n→O(n²)→O(nlogn)：先有以 i 结尾的朴素 DP（O(n²)，见后面面试追问 2），本课直接讲把“找位置”改成二分、降到 O(nlogn) 的 tails 写法。
2. 4tails[i] 表示长度 i 加 1 的递增子序列，能拥有的最小结尾。新数用二分找替换位置。
3. 5tails 为空，10 直接追加tails 是空的，10 直接追加。长度 1 的最小结尾是 10。
4. 69＜10，替换长度1的结尾9 不能让长度变长，但长度 1 的结尾从 10 降到 9，更有潜力。
5. 72 更小，继续压低结尾2 更小，继续替换长度 1 的最小结尾。
6. 85＞末尾2，接在后面长度变25 大于 tails 最后一个 2，可以接在后面，长度变成 2。
7. 9在 tails[2,5] 里二分找第一个 ≥3 的格：l=0 r=2 → mid=1 处 5≥3 → 落到下标 1关键的“定位”这一帧：3 不直接和末尾比，而是在 tails=[2,5] 里二分。l=0、r=2，mid=1 看到 tails[1]=5≥3，所以要替换的就是下标 1 这一格（高亮处）。
8. 10二分定到下标1，把长度2的结尾从5压到3二分定位到下标 1，把该格从 5 换成 3：长度没变（仍 2），但长度 2 的结尾被压低，潜力更好。
9. 11二分定到末尾(7＞末尾3)，追加，长度变3二分发现 7 比所有结尾都大（落到末尾），追加后长度变 3。tails 的长度就是当前 LIS 长度。
10. 12二分定到末尾(101＞末尾7)，追加，长度变4101 比末尾 7 还大，追加到末尾，长度变成 4——这就是答案 4 的来源，对应 [2,3,7,101]。
11. 13二分定到下标3(18＜101)，压低长度4的结尾，长度仍4最后一个数 18：二分定到下标 3，把 101 压低成 18，长度不变仍是 4。整段跑完 result=4，与题面示例完全对上。
12. 16tails 的替换不是删答案，而是在保留更好的潜力。
13. 19[2,2,2]：每个2都替换，长度恒为1[2,2,2] 每个 2 都替换第一个不小于 2 的位置，tails 长度一直是 1。
14. 26这题学完不要乱跳，下一步去 对应专题 连刷同类题；卡住时用 AI 答疑追问“为什么这一步成立”，比只背答案更稳。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def lengthOfLIS(self, nums):
        tails = []
        for x in nums:
            l, r = 0, len(tails)
            while l < r:
                m = (l + r) // 2
                if tails[m] < x:
                    l = m + 1
                else:
                    r = m
            if l == len(tails):
                tails.append(x)
            else:
                tails[l] = x
        return len(tails)

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();
    }
};

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;
        for (int x : nums) {
            int l = 0, r = size;
            while (l < r) {
                int m = (l + r) / 2;
                if (tails[m] < x) l = m + 1;
                else r = m;
            }
            tails[l] = x;
            if (l == size) size++;
        }
        return size;
    }
}

# tails[i] = 长度 i+1 的递增子序列的最小结尾(严格递增)
tails = []
for x in nums:
    pos = 二分找 tails 中第一个 >= x 的下标   # lower_bound
    if pos == len(tails):      # x 比所有结尾都大
        tails.append(x)        # 能接长 -> 追加
    else:
        tails[pos] = x         # 否则压低该长度的结尾
return len(tails)              # 长度即答案，tails 不是真实序列

// tails[i] = 长度 i+1 的递增子序列的最小结尾
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 (int)tails.size();   // 长度即答案

// tails[0..size) 各长度的最小结尾，size 即当前 LIS 长度
int[] tails = new int[nums.length];
int size = 0;
for (int x : nums) {
    int pos = lowerBound(tails, 0, size, x);   // 第一个 >= x
    tails[pos] = x;            // 落到 pos：接长或压低
    if (pos == size) size++;   // pos 在末尾 = 接长成功
}
return size;   // 长度即答案

复杂度

面试官可能追问