LC300　最长递增子序列¶

中等通过率 58.9%python3核心代码模式动态规划样例通过牛客 AC数组二分查找动态规划最长上升子序列

牛客原题　源码

讲解章节：线性 DP

一句话

维护「每种长度的最小结尾」，二分找位置替换，表长就是答案。

解题思路¶

这题考什么¶

LIS（Longest Increasing Subsequence，最长上升子序列）的两种标准解法，见线性 DP。

写法一（O(n 的平方) 的朴素 DP），思路最直白：

状态定义：f[i] = 以 nums[i] 结尾的最长严格递增子序列长度。
转移方程：

    f[i] = 1 + max(f[j])        对所有 j < i 且 nums[j] < nums[i]

没有合法的 j 时 f[i] = 1（自己单独成序列）。答案是所有 f[i] 的最大值。
必须钉死「以 nums[i] 结尾」，否则上一格的信息无法与 nums[i] 拼接。

写法二（本文件采用的 O(n log n) 贪心加二分），回应题面的进阶要求。

换一个状态：

    tails[k] = 所有长度为 k+1 的递增子序列当中，结尾元素的最小值

贪心的道理：同样长度的子序列，结尾越小越容易被后面的元素接上，
所以只保留最小的那个结尾，其余可以安全丢弃。

tails 一定是**严格递增**的：若长度 k+1 的最小结尾不小于长度 k+2 的最小结尾，
把后者截去最后一位就得到一个长度 k+1 而结尾更小的子序列，与「最小」矛盾。
既然有序，就能二分。

处理 x 时，用二分找出第一个大于等于 x 的位置 i：
    i 等于表长  ->  x 比所有结尾都大，能接在最长的那条后面，表尾追加，LIS 长度加一
    否则        ->  tails[i] = x，长度不变但结尾更小，为后续留出更多余地

**tails 不是答案序列本身**，它只是每种长度的「最优结尾」快照。
中间的替换会让不同时期的元素混进同一张表，表里元素在原数组中的先后顺序
因此得不到保证：nums = [3, 4, 1] 跑完后 tails = [1, 4]，
而 1 出现在 4 的**后面**，[1, 4] 根本不是 nums 的子序列。
表长永远是对的，表的内容只能当中间量看；要还原真正的序列必须另记前驱下标。

数据规模与复杂度¶

1 <= nums.length <= 2500，-1e4 <= nums[i] <= 1e4。朴素 DP 是 2500 的平方 / 2 约 3e6 次内层迭代，本机实测约 0.22 秒，对这个数据范围本已够用；采用二分版是为了满足题面进阶要求的 O(n log n)。时间 O(n log n) = 2500 * 12 约 3e4 次比较，空间 O(n)（tails 最长与 nums 等长）。

坑在哪¶

必须用 bisect_left 而不是 bisect_right。题目要求严格递增，遇到与某个结尾相等的 x 时，bisect_left 会把那个结尾顶掉（长度不增）， bisect_right 则会跳到它右边，把相等的元素当成「更大」接上去。 nums = [7,7,7,7,7,7,7] 用 bisect_right 会返回 7，正确答案是 1。
判断条件是 i == len(tails) 而不是 i > len(tails)。 bisect_left 的返回值范围是 0 到表长（含），等于表长就表示「插在末尾」。
追加与替换是互斥的两条路，替换时不能同时增加长度。写成无条件 append 会让 tails 变成 nums 的副本，答案退化成 n。
答案是 len(tails)，不是 tails 里的某个值，也不是 max(tails)。表长才是长度这一维的最大值。
值域含负数（-1e4 起），不能用 0 当哨兵初值来简化二分。从空表起手是最省事也最安全的写法。

样例复核¶

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

10  -> tails = [10]                （空表，追加）
9   -> 找到位置 0，替换 -> [9]
2   -> 位置 0，替换     -> [2]
5   -> 位置 1 = 表长，追加 -> [2, 5]
3   -> 位置 1（5 是第一个 >= 3），替换 -> [2, 3]
7   -> 位置 2 = 表长，追加 -> [2, 3, 7]
101 -> 位置 3 = 表长，追加 -> [2, 3, 7, 101]
18  -> 位置 3（101 是第一个 >= 18），替换 -> [2, 3, 7, 18]

返回 4，与期望输出一致。注意最后一步：长度没变，但把结尾从 101 换成 18，使得后面若再来一个 20 仍能接上——这正是「结尾越小越好」的价值。

参考实现¶

solutions/leetcode/LC300/sol.py
from bisect import bisect_left
from typing import List, Optional


class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # tails[k] = 所有长度为 k+1 的递增子序列里，结尾元素的最小值。
        # 它随下标严格递增，所以可以二分。注意 tails 本身**不是**答案序列，
        # 只是每种长度的「最优结尾」快照，要还原序列得另记前驱
        tails = []
        for x in nums:
            # 找第一个 >= x 的位置。用 bisect_left 是因为题目要求**严格**递增：
            # 等于 x 的结尾必须被顶掉，换成 bisect_right 会把相等的元素当成更大值接上，
            # 全相等的数组会算出 n 而不是 1
            i = bisect_left(tails, x)
            if i == len(tails):
                # x 比所有已知结尾都大，可以接在最长的那条后面，LIS 长度加一。
                # bisect_left 的返回值最大就是表长，所以这里是相等而非大于
                tails.append(x)
            else:
                # 长度不变，但把这一档的结尾换小，后面的元素更容易接上。
                # 这一支绝不能同时 append，否则 tails 会退化成 nums 的副本
                tails[i] = x
        # 表长就是能凑出的最大长度，答案不在表的内容里
        return len(tails)

LC300 最长递增子序列¶