LeetCode 300. 最长递增子序列：从 O(n²) 到 O(n log n) 的两级跳

最长递增子序列（Longest Increasing Subsequence，简称 LIS）大概是出现频率最高的「中等题」：它是子序列 DP 的祖师爷（编辑距离、最大子数组和都能看到它的影子），又是「贪心 + 二分」这个非常规套型的最佳示范题。同一道题，两种解法相差整整一个复杂度量级，而且第二种解法的正确性证明相当优雅——这正是它值得单开一篇的原因。

题面与约束

给你一个整数数组 nums，找出其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如 [3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

数据范围：1 <= nums.length <= 2500，-10^4 <= nums[i] <= 10^4。两个词要圈出来：严格递增（7,7 不算），子序列（可以跳着取，但相对顺序不能变）。n <= 2500 意味着 O(n²) 的六百万次运算完全跑得动——这是这题的底线解法；而官方的进阶追问「能否做到 O(n log n)」才是这道题的灵魂。

官方示例三个：[10,9,2,5,3,7,101,18] 输出 4（如 [2,3,7,101]）；[0,1,0,3,2,3] 输出 4（[0,1,2,3]）；[7,7,7,7,7,7,7] 输出 1（严格递增，重复元素一个都扩不进去）。

O(n²)：状态必须「钉」在结尾上

很多人第一次做 LIS 会卡在状态设计上：「以 [0..i] 为前缀的最长递增子序列」为什么不行？因为光知道长度不够——你不知道这条子序列的结尾是几，就没法判断 nums[i] 能不能接上去。所以状态要钉得更细：

f[i] = 以 nums[i] 结尾的最长严格递增子序列的长度

定义里强制包含 nums[i] 自己，递推才有抓手：所有在 i 左边、值比 nums[i] 小的位置 j，都可以作为 nums[i] 的前驱，取其中最优的接上去：

f[i] = 1 + max(f[j])，其中 j < i 且 nums[j] < nums[i]；不存在则 f[i] = 1

答案不是 f[n-1]——最长的子序列不一定以最后一个元素结尾，要对整个 f 取最大值。这两处（结尾钉死、全局取 max）是 DP 解法最容易写错的细节：

class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        n = len(nums)
        f = [1] * n                    # 每个元素自己就是长度 1 的子序列
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:  # 严格递增：必须小于
                    f[i] = max(f[i], f[j] + 1)
        return max(f)

时间 O(n²)、空间 O(n)。它教会我们的通用一课是：当「只看位置」的状态推不动时，把状态的语义加细到「以每个位置为结尾」。这一招在站内题解里已经登场过两次——LeetCode 53. 最大子数组和的 Kadane 定义「以 i 结尾的最大和」、LeetCode 70. 爬楼梯的「到第 i 阶的方案数」——LIS 是它的第三次亮相，也是把「钉结尾」用到极致的一次。

这个递推还有一个图论的读法：把每个元素看成一个点，j < i 且 nums[j] < nums[i] 就连一条有向边 j → i，整个数组变成一张有向无环图（DAG），LIS 就是这张图上的最长路。「子序列问题 = DAG 最长路」是 DP 里的一座桥：桥的这头是 O(n²) 的暴力松弛，桥的那头是各类图上 DP。

O(n log n)：维护「最有潜力的结尾」

换一个视角：与其问「每个元素结尾的最长是多少」，不如反过来问——「长度为 k 的递增子序列，最短能以几结尾？」 结尾越小，后面能接上来的元素就越多，潜力越大。维护这个问题的答案数组 tails：

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

tails 本身严格递增，这是整个算法能二分的根基，值得把证明补全：设长度 k+1 的最小结尾是 a，长度 k+2 的最小结尾是 b。反设 b <= a：把长度 k+2 的那条子序列去掉最后一个元素 b，剩下的是一条长度 k+1 的递增子序列，且它的结尾严格小于 b <= a——与「a 是长度 k+1 的最小结尾」矛盾。所以 tails[k] < tails[k+1] 对所有 k 成立。

严格递增意味着可以二分。对每个新元素 x，在 tails 里找第一个 >= x 的位置：

找不到（x 比所有结尾都大）：x 能把目前最长的子序列延长一格，tails 追加 x；
找到了：把那个位置替换成 x——同长度下换一个更小的结尾，潜力只增不减。

替换不会破坏「最小结尾」的定义，因为被换掉的值本来就 >= x。整个算法每个元素只做一次二分：

from bisect import bisect_left

class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        tails = []  # tails[k]：长度 k+1 的严格递增子序列的最小结尾
        for x in nums:
            pos = bisect_left(tails, x)   # 第一个 >= x 的位置
            if pos == len(tails):
                tails.append(x)           # 比所有结尾都大，最长长度 +1
            else:
                tails[pos] = x            # 同长度换更小的结尾
        return len(tails)

拿官方示例 1 完整走一遍，tails 的演化是：

x = 10  →  [10]
x = 9   →  [9]                # 9 < 10，长度 1 换更小结尾
x = 2   →  [2]
x = 5   →  [2, 5]             # 5 比所有结尾大，长度 +1
x = 3   →  [2, 3]
x = 7   →  [2, 3, 7]          # 长度 +1
x = 101 →  [2, 3, 7, 101]     # 长度 +1
x = 18  →  [2, 3, 7, 18]      # 注意！

读一遍轨迹会发现：三处「换更小结尾」（10→9→2、5→3、101→18）没有一处增加长度，但每一次替换都让后续扩展更容易——贪心的全部收益都藏在这些替换里。整个算法的正确性可以收拢成一条循环不变量：处理完前 i 个元素后，tails[k] 恰等于「前 i 个元素中长度为 k+1 的递增子序列的最小结尾」。归纳基础（空数组）显然，归纳步只有两种操作（延长最长链、改进某一级结尾）且上文都已论证不破坏定义，因此 len(tails) 就是整个前缀的 LIS 长度。复杂度上，每个元素恰好做一次 O(log n) 的二分加一次 O(1) 的增/改，总计 O(n log n)——注意二分的规模是 tails 的长度而不是原数组，这也是它快过 DP 内层 O(n) 扫描的原因。

时间 O(n log n)、空间 O(n)。在同一台机器上（n = 2500，随机数据）实测：DP 约 98ms，贪心 + 二分约 0.2ms——差了约 540 倍，这正是复杂度量级差的直观样子。顺带说一道面试常考的换算：1 秒大约容纳 10^8 次基本运算，O(n²) 在 n = 2500 时是约 6×10^6 次，怎么都稳；但数据范围若放大到 10^5，O(n²) 就是 10^10 次，必须换 O(n log n)。数据范围本身就是出题人在暗示解法——这是读题的第一课。

三个高频易错点

第一，tails 不是 LIS 本身。看演化最后一步：[2, 3, 7, 101] 里的 101 被换成了 18，但原数组里 18 在 7 与 101 的后面，接不到 [2,3,7] 后面。tails 只保证长度正确，其中元素可能来自数组的「不同时间线」，不能当真实子序列用。要还原方案，见下一节。

第二，严格递增用 bisect_left，非严格递增才用 bisect_right。这题要求严格递增，等值元素必须「放左边、替换掉」，所以用 bisect_left（找第一个 >= x 的位置，等值会被替换）。如果题目改成「非严格递增」（允许相等），等值元素可以接在末尾，就要换成 bisect_right（找第一个 > x 的位置，等值会被追加或放到右侧）。一行之差，全 7 数组的答案可能从 1 变成 7，是这题最阴的变体陷阱。顺带一个跨语言提醒：Python 的 bisect_left 直接给出「第一个 >= x」的位置，C++ 也有现成的 std::lower_bound；但 Java 的 Arrays.binarySearch 找到时返回的是「任意一个匹配位置」（不保证最左），找不到时返回 -(插入点) - 1——Java 选手必须自己封装一个 lowerBound，照搬内建二分是非 Python 语言里最常见的错误来源。

第三，别把 O(n²) 的内层循环写成「找全局最大 f[j]」。前驱必须同时满足 j < i 和 nums[j] < nums[i] 两个条件，漏了顺序约束就会把后面的元素接到前面去。

进阶：把一条真实的 LIS 还原出来

面试官常在追问里要一条具体的 LIS。做法是把 tails 拆成两个平行数组（一个记最小结尾的值，一个记该结尾在原数组里的下标），再给每个元素记一个 prev 前驱指针——新元素落到位置 pos 时，它的前驱就是当时长度为 pos 的方案记录的结尾下标。最后从最长方案的结尾沿 prev 回跳：

from bisect import bisect_left

def lis_reconstruct(nums):
    n = len(nums)
    if n == 0:
        return 0, []
    tails_val, tails_idx = [], []   # 平行数组：长度 k+1 的最小结尾值 / 该结尾的下标
    prev = [-1] * n                 # prev[i]：以 i 结尾的 LIS 里 i 的前驱下标
    for i, x in enumerate(nums):
        pos = bisect_left(tails_val, x)
        prev[i] = tails_idx[pos - 1] if pos > 0 else -1  # 先记前驱再改 tails
        if pos == len(tails_val):
            tails_val.append(x); tails_idx.append(i)
        else:
            tails_val[pos] = x; tails_idx[pos] = i
    seq, cur = [], tails_idx[-1]    # 从最长方案的结尾回跳
    while cur != -1:
        seq.append(nums[cur])
        cur = prev[cur]
    return len(seq), seq[::-1]

对示例 1 它返回 (4, [2, 3, 7, 18])——不是题解里写的 [2, 3, 7, 101]，但完全合法：LIS 从来不唯一，任何声称「返回唯一正确方案」的实现都值得怀疑。这段代码在本地跑了 5000 轮随机对拍，验证三件事：返回的序列严格递增、确实是原数组的子序列、长度与 O(n²) DP 一致。

LIS 的现实身影

这个「纸牌游戏」出身的数据结构（tails 的维护过程就是 1960 年代的 patience sorting 纸牌接龙）在工程里有一个大名鼎鼎的应用：Patience Diff。Bram Cohen（BitTorrent 作者）为 Bazaar 版本控制工具设计的 diff 算法，不用逐行最短编辑距离，而是先在两个版本中找出唯一出现过的相同行，对这些行的匹配求最长递增子序列作为对齐锚点，再对锚点之间的小段递归做普通 diff。这样产出的补丁更贴近人类的重构意图（比如不把函数挪动拆成删一半加一半），git diff --patience 与 JGit 的 histogram diff 都是这一思想的后续。

数学上 LIS 还有个漂亮的彩蛋：对一个随机打乱的排列，LIS 的期望长度渐近于 2√n（Logan–Shepp 与 Vershik–Kerov 在 1977 年各自证明），其涨落服从 Tracy–Widom 分布（Baik–Deift–Johansson，1999）。也就是说 n = 2500 的随机数据里，最长的递增子序列大约只有 100 上下——二分解法里 tails 数组远比想象中短。

变体速览与结语

同一套骨架上长出来的两个官方变体值得一并刷：673. 最长递增子序列的个数在 f 旁边再维护一个计数数组 cnt[i]（f[j] + 1 == f[i] 时条数相加，f[j] + 1 > f[i] 时条数归一），拿 [1,3,5,4,7] 一数便知：长度 4 的子序列有 [1,3,5,7] 与 [1,3,4,7] 两条，答案是 2——「条数」这种 DP 值表达不了的量，靠并列状态相加就能长出来；354. 俄罗斯套娃信封是二维 LIS——按宽升序、宽相同按高降序排序后对高求 LIS，降序这步正好挡住「同宽信封互相嵌套」的非法转移，是「排序预处理 + 一维 LIS」的教科书组合。

回头看，LIS 的两级跳对应两种通用思维：DP 教你把状态定义到足够细（细到「以 i 结尾」，递推才推得动），贪心 + 二分教你换一个问题（从「多长」换成「每个长度最小结尾是几」），换完之后单调性自己浮出水面，二分顺理成章。再加上「tails 不是方案本身」、bisect_left / bisect_right 的严格性之分和前驱指针还原，这道题的可考点比它的题面丰富得多——这也是它十几年一直是面试常客的原因。

参考资料

300. Longest Increasing Subsequence — LeetCode：原题面、数据范围与官方进阶追问。
Longest increasing subsequence — cp-algorithms：O(n log n) 解法的严格证明与还原具体方案的做法。
Patience sorting — Wikipedia：tails 数组的原始出处与 Patience Diff 的来龙去脉。
Longest increasing subsequence — Wikipedia：随机排列 LIS 期望长度 2√n 与 Tracy–Widom 分布的定理条目。
673. Number of Longest Increasing Subsequence — LeetCode：计数数组变体。
354. Russian Doll Envelopes — LeetCode：二维 LIS 变体，排序技巧的经典应用。