开发者日记

外观

从 O(n²) 到 O(nlogn)：一文搞懂 LIS 贪心二分 ​

为什么 LIS 是动态规划与二分优化的经典题 ​

最长递增子序列（Longest Increasing Subsequence，简称 LIS）要求在一个数组中，找出元素严格递增、且不要求连续的最长子序列。例如 [10, 9, 2, 5, 3, 7, 101, 18] 的最长递增子序列长度是 4，如 [2, 3, 7, 101]。

这道题之所以高频，是因为它同时覆盖两类核心能力：

  1. 动态规划建模能力：用 dp[i] 表示以第 i 个元素结尾的 LIS 长度；
  2. 贪心与二分优化能力：维护不同长度下的最小结尾值，把内层线性扫描降为二分查找。

很多同学能背出 tails 数组写法，却不理解为什么“替换”不会破坏真实序列，也不知道如何还原具体方案。本文从 O(n²) 动态规划出发，逐步推导 O(nlogn) 的耐心排序思想。

方案一：动态规划，最直观的 O(n²) 解法 ​

状态定义与转移方程 ​

定义：

text
dp[i]：以 nums[i] 结尾的最长递增子序列长度

因为子序列可以接在任意更早且更小的元素后面，所以：

text
当 j < i 且 nums[j] < nums[i] 时：
dp[i] = max(dp[i], dp[j] + 1)

每个元素自身构成长度为 1 的子序列，因此 dp 初始值全为 1。

可运行 Python 代码 ​

python
def length_of_lis_dp(nums):
    if not nums:
        return 0

    n = len(nums)
    # dp[i] 表示以 nums[i] 结尾的 LIS 长度
    dp = [1] * n
    answer = 1

    for i in range(n):
        for j in range(i):
            # 严格递增：前一个元素必须小于当前元素
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j + 1] if False else dp[j] + 1)
        answer = max(answer, dp[i])

    return answer


nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(length_of_lis_dp(nums))  # 4

上面代码中 dp[j] + 1 是核心转移；刻意保留的 if False 没有实际意义，实际编写时直接写 dp[j] + 1 即可。更清晰的正式版本如下：

python
def length_of_lis_dp_clean(nums):
    if not nums:
        return 0

    dp = [1] * len(nums)

    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

复杂度与适用场景 ​

  • 时间复杂度：O(n²)，两层循环枚举当前位置和前驱位置；
  • 空间复杂度：O(n)，需要 dp 数组；
  • 优点：逻辑直观，适合理解子序列类动态规划；
  • 缺点：当 n 达到 10^5 时，约 10^10 次比较，通常会超时。

方案二：耐心排序思想，维护最小结尾值 ​

贪心直觉：结尾越小，未来越容易接元素 ​

假设我们已经有两个长度相同的递增子序列：

text
序列 A：[2, 9]
序列 B：[2, 5]

它们长度都为 2，但 [2, 5] 的结尾更小。未来如果出现 7，序列 B 可以扩展为 [2, 5, 7]，而序列 A 不能。

因此，对于每一种长度，我们只关心一个信息：能够形成该长度的最小结尾值。

维护数组 tails：

text
tails[k] 表示长度为 k + 1 的递增子序列的最小可能结尾值

tails 始终保持严格递增。

处理规则 ​

遍历每个数字 x：

  1. 如果 x 大于 tails 最后一个元素，说明可以延长最长递增子序列，直接追加；
  2. 否则，在 tails 中找到第一个大于等于 x 的位置，并用 x 替换它；
  3. 替换不是修改某个真实子序列，而是更新“某长度的最小结尾”。

查找第一个大于等于 x 的位置，正是二分查找中的 lower_bound。

遍历元素 x读取 nums[i]x 大于 tails 末尾？判断能否延长是：append(x)，长度增加否：二分找 lower_bound替换第一个 ≥ x 的值tails 始终递增最终 tails 长度即 LIS 长度

O(nlogn) 贪心二分代码推导 ​

使用 bisect_left 计算长度 ​

Python 标准库中的 bisect_left 对应 lower_bound：返回第一个大于等于目标值的位置。

python
from bisect import bisect_left


def length_of_lis_binary_search(nums):
    # tails[len - 1] 表示长度为 len 的递增子序列的最小结尾
    tails = []

    for x in nums:
        pos = bisect_left(tails, x)

        if pos == len(tails):
            # x 比所有结尾都大，可以延长当前最长序列
            tails.append(x)
        else:
            # 降低某一长度的最小结尾，为未来元素留出空间
            tails[pos] = x

    return len(tails)


nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(length_of_lis_binary_search(nums))  # 4

用数组手动模拟二分过程 ​

以输入 [10, 9, 2, 5, 3, 7, 101, 18] 为例：

text
10  -> tails = [10]
9   -> tails = [9]
2   -> tails = [2]
5   -> tails = [2, 5]
3   -> tails = [2, 3]
7   -> tails = [2, 3, 7]
101 -> tails = [2, 3, 7, 101]
18  -> tails = [2, 3, 7, 18]

最终 tails 长度为 4，所以答案是 4。注意最后数组 [2, 3, 7, 18] 恰好也是一个真实 LIS，但在更多数据中，tails 本身不一定等于真实的最长递增子序列，它首先是一张“最小结尾表”。

不用标准库：手写二分边界 ​

python
def length_of_lis_manual_binary_search(nums):
    tails = []

    for x in nums:
        left, right = 0, len(tails)

        # 寻找第一个大于等于 x 的位置
        while left < right:
            mid = (left + right) // 2
            if tails[mid] < x:
                left = mid + 1
            else:
                right = mid

        if left == len(tails):
            tails.append(x)
        else:
            tails[left] = x

    return len(tails)

这里使用左闭右开区间 [left, right)，循环结束时 left == right，即 lower_bound 位置。

复杂度分析 ​

  • 每个元素执行一次二分查找：O(logn)；
  • 总共处理 n 个元素：O(nlogn)；
  • tails 最长为 n：空间复杂度 O(n)。

如何还原一条真实的最长递增子序列 ​

如果题目只要长度，直接返回 len(tails)；如果要求输出具体序列，就不能简单认为 tails 一定是答案。可以额外记录每个元素被放入 tails 时对应的长度，再倒推前驱。

python
from bisect import bisect_left


def build_lis(nums):
    tails = []              # 最小结尾表
    tail_indices = []       # 对应结尾元素在 nums 中的下标
    prev = [-1] * len(nums) # 当前元素选择的前驱下标
    lengths = [0] * len(nums)  # 当前元素能形成的 LIS 长度

    for i, x in enumerate(nums):
        pos = bisect_left(tails, x)

        if pos == len(tails):
            tails.append(x)
            tail_indices.append(i)
        else:
            tails[pos] = x
            tail_indices[pos] = i

        lengths[i] = pos + 1
        if pos > 0:
            prev[i] = tail_indices[pos - 1]

    # 从最终最长长度对应的最后一个位置倒推
    last_index = tail_indices[-1]
    result = []

    while last_index != -1:
        result.append(nums[last_index])
        last_index = prev[last_index]

    result.reverse()
    return result


print(build_lis([10, 9, 2, 5, 3, 7, 101, 18]))
# 可能输出：[2, 3, 7, 18]

倒推的关键是：当元素占据 tails[pos] 时，它可以接在长度 pos 的最优结尾之后，因此其前驱来自 tail_indices[pos - 1]。

动态规划与贪心二分如何选型 ​

O(n²) 动态规划状态清晰，便于方案统计O(nlogn) 贪心二分适合 n 很大、只求长度需要计数/特殊限制优先考虑 DP 扩展只求最长长度优先 tails + 二分

简单决策原则：

  • n ≤ 2000，且题目需要统计方案数、带限制转移，动态规划通常更稳；
  • n ≥ 10^5，只问最长长度，优先贪心二分；
  • 需要还原具体序列时，在二分过程中额外记录前驱；
  • 如果题目改成最长非递减子序列，比较条件和二分函数都要同步调整。

避坑总结：高频错误现象与修正方法 ​

1. 把严格递增写成非递减 ​

错误现象： 输入 [2, 2]，严格 LIS 长度应为 1，却得到 2。

常见错误是 DP 中写成：

python
if nums[j] <= nums[i]:  # 错误：这是非递减
    dp[i] = max(dp[i], dp[j] + 1)

修正方法： 严格递增必须使用 <，二分优化必须使用 bisect_left。如果题意是非递减，则 DP 改为 <=，二分改为 bisect_right。

2. 误以为 tails 一定是一条真实 LIS ​

错误现象： 某些替换发生后，tails 中的元素可能来自时间顺序不一致的多个候选序列，直接返回 tails 可能不是合法子序列。

修正方法： 只求长度时，len(tails) 始终可靠；要求具体方案时，记录 prev 和每个位置对应的长度，再从最长位置倒序还原。

3. 手写二分漏掉空数组或边界 ​

错误现象： right 初始化成 len(tails) - 1，空数组时访问越界；或者循环条件写成 left <= right，却没有正确处理插入位置。

修正方法： 推荐固定使用左闭右开写法：

python
left, right = 0, len(tails)
while left < right:
    mid = (left + right) // 2

这样即使 tails 为空，也会自然得到插入位置 0。

4. 只背模板，不理解替换含义 ​

错误现象： 看到元素没有让 tails 变长，就认为处理无效；实际上替换可能降低某个长度的结尾，为后续更长序列创造条件。

修正方法： 牢记 tails[pos] = x 的含义是“长度 pos + 1 的最小结尾变得更小”，不是“把当前真实 LIS 的某个元素改掉”。

结语 ​

LIS 的 O(n²) 动态规划解决的是“从哪些前驱转移”的问题，而 O(nlogn) 贪心二分解决的是“如何快速维护最优状态”的问题。前者适合打牢状态转移基础，后者体现了耐心排序中按牌堆维护最小牌面的思想。

真正掌握这道题，不只是记住 bisect_left，而是能解释清楚三件事：为什么只保留最小结尾、为什么替换不影响答案长度、以及需要具体方案时如何通过前驱数组还原。

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。

本文来自开发者日记（devdiary.cn）· 记录开发者实战笔记与免费在线工具箱

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。