最长递增子序列LIS：动态规划与贪心二分解法全解析

力扣热题100里排在第87位的这道最长递增子序列原题号其实是300. Longest Increasing Subsequence。我刷到这一题的时候有点意外——大名鼎鼎的LIS居然在热题100里藏得这么靠后。不过位置靠后不代表它简单这几乎是动态规划入门绕不开的关卡也是面试里“线性dp”最常考的原型之一。更妙的是它同时能让你看到动态规划和贪心两种截然不同的解题风格一棵树上开两朵花。题目本身一句话就能说清楚给定一个整数数组找出其中最长严格递增子序列的长度。这里“子序列”不要求连续但必须保持原始数组中的相对顺序。如果你是刚开始刷动态规划的人这道题值得作为“状态设计”的第一课如果你已经在背模板、准备面试那贪心加二分的写法就是你必须掌握的复杂度优化再进一步如果你想知道为什么有时候贪心数组里的内容并不能直接当答案输出这篇文章也会把坑填上。1. 题目解读与两种思路的全局观1.1 先弄清楚“子序列”和“严格递增”意味着什么给你一个例子就明白了。nums [10, 9, 2, 5, 3, 7, 101, 18]它的最长递增子序列长度是4比如[2, 3, 7, 101]也可以是[2, 3, 7, 18]。注意这里跳过了很多数字9和10因为出现在2之前所以没法参与后续的递增101虽然大但18在它后面所以如果选了101后面只能走到101结束。这里有两个关键词容易被新手忽略。第一个是“子序列”。子序列不需要在原数组里连续只要下标顺序不乱就行。所以你不能用“连续最大上升子数组”的思路去套。连续问题往往靠一个滑动窗口或一次遍历就能维护但子序列问题天然就要考虑“跳过中间元素”的可能这也是为什么线性dp会把每个位置当作一个独立状态来设计。第二个是“严格递增”。严格递增意味着nums[j] nums[i]而不是。如果数组是[1, 1, 1]答案不是3而是1。很多人在二分优化那里翻车就是因为没分清“严格递增”和“非递减”后面我会专门讲。1.2 为什么这道题值得用两种解法反复刷这道题好在哪好在它用最少的代码量把动态规划的两个核心概念都塞进去了状态定义和状态转移。你只要想明白dp[i]是以nums[i]结尾的最长递增子序列长度转移方程几乎自己就出来了。但它又能继续往下挖当n来到十万级别O(n^2)是肯定跑不过的这时候需要换一个思路用贪心维护一个“最小末尾值”数组再配合二分查找把复杂度降到O(n log n)。很多刷题的人只背了优化解法却说不清为什么 tails 数组的长度就是答案。我建议你把两种解法都亲手写一遍尤其是用同一个测试用例去逐步打印数组你会直观看到“替换”比“追加”更聪明在哪。2. 动态规划O(n²) 的朴素但直观解法2.1 dp 状态定义以 nums[i] 结尾动态规划的第一步永远是设计状态。LIS 里最常见的状态是dp[i] 表示以 nums[i] 作为最后一个元素的最长递增子序列长度。为什么一定要“以 nums[i] 结尾”而不直接定义成“前 i 个元素里的最长递增子序列长度”因为递增子序列能不能继续往后扩展取决于当前最后一个元素的值。如果你只记录前 i 个元素的最大长度那这个最大长度对应的结尾数字是多少不知道。后面再来一个更大的数字你也没办法判断能不能接上去。举个例子前三个元素是[5, 1, 2]前两个元素的最长子序列是[5]长度1结尾是5但前三个元素的最长子序列是[1, 2]长度2结尾是2。如果新来一个数字3它能接到结尾2后面形成长度3却接不到5后面。所以你光记一个“前 i 个最大长度”远远不够必须把每个可能的结尾都记下来。这就是“以 i 结尾”的真正原因它把子序列的边界信息保留在状态里保证后续转移时有据可依。这种设计在线性dp里非常常见练熟这道题后面很多字符串、区间 dp 都会用到类似套路。2.2 状态转移方程与代码模板状态转移其实就是在做一件事枚举所有可能接在nums[i]前面的元素nums[j]如果nums[j] nums[i]那么nums[i]可以接在以nums[j]结尾的子序列后面长度就是dp[j] 1。初始情况下每个元素自身可以单独构成一个长度为1的子序列所以dp[i] 1。转移式可以写成dp[i] max(dp[i], dp[j] 1) 其中 0 j i 且 nums[j] nums[i]完整代码from typing import List class Solution: def lengthOfLIS(self, nums: List[int]) - int: if not nums: return 0 n len(nums) dp [1] * n for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)最后返回的是max(dp)不是dp[-1]。因为答案不一定是以最后一个元素结尾的子序列比如[1, 3, 6, 7, 9, 4, 5, 6]以最后一个6结尾的最长长度可能是4但全局最长是5结尾在9那里。2.3 复杂度分析和几个容易忽略的细节时间上是两层循环外层遍历 i总共 n 个元素内层枚举 j 从 0 到 i-1平均 n/2 次。所以时间复杂度是O(n^2)空间复杂度O(n)。这个复杂度在力扣原题的n 2500下足够通过但一旦数据量到10^5级别就悬了。写这段代码时有几个细节值得注意。第一内层循环必须遍历所有 j而不是只看i-1。因为递增子序列可以跳过很多中间元素nums[i]可能接在很前面的某个小数字后面。比如[2, 1, 3]当 i2 时nums[2]3它不仅能接在1后面也能接在2后面两个都要比较。第二转移条件是nums[j] nums[i]等号不能算。如果数组里有大量重复元素比如[2, 2, 2]那么所有 j 都不满足严格小于三个 dp 值都是1最终结果就是1。第三dp[i]在循环过程中可能会被多次更新所以用max来取最优。不能直接把dp[j] 1赋值给dp[i]因为可能后面枚举到更长的 j也可能一个都不满足。3. 贪心 二分从 O(n²) 降到 O(n log n)3.1 维护“最小末尾值”数组的贪心思想这一小节是整个题解里最值得反复琢磨的部分。我们先改变思路不关心具体最长子序列长什么样只关心“在长度固定时能不能让它的末尾元素尽可能小”。末尾越小后面能接的数字范围就越大越有可能形成更长的子序列。这个思想说白了就是贪心每一步都让当前状态的“潜力”最大化。实现上维护一个数组tailstails[k] 表示长度为 k1 的递增子序列中最小的末尾元素值。这里有个很关键的理解tails数组本身不一定是真实存在的某个递增子序列它只是记录“每个长度对应的最优秀末尾值”。我们只拿它的长度作为答案不拿内容当真。遍历每个x做这样一件事如果x比tails里所有元素都大说明它可以接到当前最长子序列后面于是追加到末尾最长长度加1否则找到第一个大于等于x的位置用x替换掉那个位置的值。替换看起来有点“反悔”因为本来某个位置已经有一个末尾值了现在来了个更小的就把原来那个赶走。这种“当前不是最优就换一个更优的”思路和信奥里常说的反悔贪心有异曲同工的感觉。为什么替换不会破坏已有长度因为替换只发生在长度不变的位置上没有丢掉已经获得的长度只是降低该长度的末尾值让它对后续扩展更友好。我习惯用扑克牌来理解这个操作你有好几堆牌每堆的堆顶记录了“当前这堆的最小顶牌”。新来一张牌如果比所有堆顶都大就新开一堆否则放到第一张比它大的牌所在的那堆上把原来的顶牌压下去。牌堆的数量就是最长递增子序列的长度。这个玩法有个正式的名字叫耐心排序。3.2 二分查找用 bisect_left 还是 bisect_right因为tails是严格递增的所以可以用二分查找加速。Python 里直接用bisect模块from bisect import bisect_left pos bisect_left(tails, x)这里必须用bisect_left它返回第一个大于等于x的下标。如果数组允许非递减例如让你求“最长非递减子序列”那要改成bisect_right它返回第一个大于x的下标这样相同元素可以接在后面。怎么快速记住bisect_left会把相等的元素当作“可以替换”所以最终序列里不会保留相等的两个值bisect_right会把相等的元素当作“可以追加”所以非递减场景用它。本题的“严格递增”对应bisect_left。还有一个常见写法是if not tails or x tails[-1]: tails.append(x) else: pos bisect_left(tails, x) tails[pos] x这个写法是在做显式判断逻辑上也完全没问题。但我个人更喜欢直接用bisect_left返回的位置判断pos bisect_left(tails, x) if pos len(tails): tails.append(x) else: tails[pos] x这样少一次额外比较代码也更对称。3.3 完整代码与模拟运行完整代码如下from typing import List from bisect import bisect_left class Solution: def lengthOfLIS(self, nums: List[int]) - int: tails [] for x in nums: pos bisect_left(tails, x) if pos len(tails): tails.append(x) else: tails[pos] x return len(tails)用[10, 9, 2, 5, 3, 7, 101, 18]完整跑一遍看看 tails 怎么变x10: tails [10] x9: bisect_left([10], 9) 0替换 - [9] x2: bisect_left([9], 2) 0替换 - [2] x5: bisect_left([2], 5) 1末尾追加 - [2, 5] x3: bisect_left([2, 5], 3) 1替换 - [2, 3] x7: bisect_left([2, 3], 7) 2追加 - [2, 3, 7] x101: bisect_left([2, 3, 7], 101) 3追加 - [2, 3, 7, 101] x18: bisect_left([2, 3, 7, 101], 18) 3替换 - [2, 3, 7, 18]最后tails [2, 3, 7, 18]长度4答案4。这里很巧合tails本身也是一个真实的最长递增子序列但后面我会告诉你这个“巧合”不能被当成普遍规律。4. 两种解法对比与适用场景4.1 时间、空间、代码量对比我把两种解法放在一张表里方便你一眼看清差别对比项动态规划贪心 二分时间复杂度O(n²)O(n log n)空间复杂度O(n)O(n)代码量短容易背更短但理解门槛高是否容易输出具体序列容易可记录前驱需要额外维护前驱稍复杂适用数据规模n 几千以内n 十万甚至百万适合初学者强烈推荐先学建议掌握 dp 后再学如果你只是应付力扣原题n 2500两种都能过。但在面试回答时我一般建议先用动态规划讲清楚状态再说“如果数据量大可以用贪心加二分优化到 O(n log n)”。这个回答过程本身就展示了你的思路层次。4.2 能不能通过贪心数组重新构造出真实序列很多人刷完题会有一个疑问tails数组里存的不就是最长递增子序列吗为什么很多题解说不能直接用问题出在替换操作上。tails里的每个元素只是“当前长度下的最小末尾值”这些值来自不同历史阶段的元素组合起来不一定保持在下标上递增也不一定真的能形成一条合法的子序列。举个反例nums [3, 1, 2, 0, 4]跑一遍贪心x3: tails [3] x1: 替换 - [1] x2: 追加 - [1, 2] x0: 替换 - [0, 2] x4: 追加 - [0, 2, 4]最后tails [0, 2, 4]长度3答案确实是3。但你在原数组里能找到[0, 2, 4]这个子序列吗0的下标在2的后面2的下标在4的前面所以按照原数组顺序[0, 2, 4]根本不是一个合法子序列。真实答案可以是[1, 2, 4]或[0, 4]再加一个凑长度反正长度是3。这就是为什么tails只配当“长度计数器”不能当答案输出。如果你真的需要输出一个具体子序列有两个办法用动态规划的状态转移同时维护一个prev[i]数组记录每个dp[i]是从哪个 j 转移过来的最后倒序回溯用贪心的变体“耐心排序”在替换时额外记录每个元素的前驱下标最后从最后一堆的顶部开始回溯。第一种写起来更直白大多数面试场景已经够用def lis_with_path(nums): if not nums: return [] n len(nums) dp [1] * n prev [-1] * n end 0 for i in range(n): for j in range(i): if nums[j] nums[i] and dp[j] 1 dp[i]: dp[i] dp[j] 1 prev[i] j if dp[i] dp[end]: end i path [] cur end while cur ! -1: path.append(nums[cur]) cur prev[cur] return path[::-1]注意prev[i]的更新要和dp[i]的更新同步不能只比较大小忘了记录来源。而且如果出现多个 j 都能提供相同长度任选一个即可得到的子序列不一定唯一但长度一定对。4.3 什么时候该用哪种解法我的选择标准很简单只要求最长长度而且数组很长、数据量达到10^5以上用贪心加二分题目要求输出具体的子序列或者要求你给出所有可能长度的信息优先用动态规划因为它天然保留每个位置的状态如果是面试手撕代码先写动态规划让面试官看到思路再提优化不要一上来就甩贪心二分容易让人觉得你在背模板。另外还有一种折中你可以先写O(n^2)的 dp 验证思路再写一个贪心二分的方法做对照用随机数据对比两个结果是否一致。这是我很喜欢的自测方式能快速发现自己对边界条件的理解有没有出问题。5. 实战中容易踩的坑与调试技巧5.1 空数组、单元素数组的边界处理力扣原题数组长度至少为1所以很多人会忽略空数组。但在本地测试、或者把代码改成工具函数时空数组必须考虑。动态规划写法里如果nums为空直接返回0否则dp[0]会越界贪心写法天然支持空数组因为tails为空循环不执行返回len(tails)就是0单元素数组两种写法都返回1不会出错。别小看这个边界很多人在面试现场写 dp 时忘记判空结果被测试用例打脸。养成习惯拿到一个数组类题目先问自己数组能不能为空能的话就在入口处理掉。5.2 重复元素对“严格递增”的影响如果题目把“严格递增”换成“非递减”整个解法的行为都会变。看一个极端例子nums [4, 4, 4, 4]严格递增答案是1因为任何两个4都不能构成递增关系。如果用动态规划转移条件是nums[j] nums[i]所有4之间都不满足所以 dp 全是1。如果用贪心加二分并且正确使用bisect_left第一个4会放到索引0后面的4也都会bisect_left到索引0然后不断替换数组长度一直是1。但如果你误用bisect_right第二个4就会追加到后面tails会变成[4, 4]得到错误答案2。这是二分写法里最经典的翻车点。所以每次写完都用一个全是相同数字的用例去测一下能立刻暴露问题。5.3 二分法下标越界和返回值的坑bisect_left的返回值范围是[0, len(tails)]。返回len(tails)时说明x比 tails 中所有元素都大应该追加返回其他值时说明找到了第一个大于等于x的位置用x替换。新手容易在判断条件上犯错# 错误写法 if pos len(tails): tails.append(x)这永远不会成立因为pos最多等于len(tails)不会大于。正确写法是if pos len(tails)。还有一种常见写法是if x tails[-1]: tails.append(x) else: tails[bisect_left(tails, x)] x这里要求使用前保证tails非空。如果tails为空tails[-1]会直接抛异常需要额外加判断。所以用我前面给的那种统一写法会更省心不用管数组空不空。5.4 调试技巧打印 tails 和 dp我刷这道题时最喜欢做的一件事就是写一个辅助函数打印中间状态特别是贪心解法def debug_lis(nums): tails [] for i, x in enumerate(nums): pos bisect_left(tails, x) if pos len(tails): tails.append(x) else: tails[pos] x print(fi{i}, x{x}, tails{tails}) return len(tails)这段输出能很直观地告诉你哪个元素触发了替换哪个元素触发了追加也能让你快速发现为什么有些时候 tails 内容不是真实序列。动态规划那边则可以打印dp数组对照去看每一个位置的转移来源。比如[1, 3, 2, 4]的 dp 值会是[1, 2, 2, 3]你能看到最后一个4可以接到多个位置后面但最长的是接在1后面形成的长度3。6. 延伸思考从这道题到更多变体6.1 最长递增子序列的常见变体LIS 的原型很简单但它的变体非常多而且都是面试和竞赛里的常客。第一类是“二维化”。比如力扣354题“俄罗斯套娃信封问题”信封有宽和高信封A能套进信封B需要宽、高都严格小于B。这个题要先按宽度升序、宽度相同时高度降序排序然后对高度数组求 LIS。排序的目的就是把二维问题降成一维再套用标准的 LIS。第二类是“带权最值”。比如求“最大递增子序列和”不是求最长长度而是求递增子序列的最大元素和。这时候 dp 状态不再从1起跳而是从nums[i]起跳dp[i] nums[i] for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] nums[i])第三类是“可相等”。比如求最长非递减子序列只要把转移条件改成贪心那边的二分也改成bisect_right即可。还有更进阶的变体比如二维平面上求最大递增链、在树或 DAG 上求最长路径本质上都能回到 LIS 的状态设计思路上来。6.2 贪心思想在周赛里有多常见你可能在热词里看到过“反悔贪心”“周赛430”之类的说法。这类题目在周赛里频繁出现其实不是偶然。LIS 的贪心写法就是一种很朴素的“反悔模型”我先把某个长度下的末尾值固定下来后来遇到更小的合适值就替换掉。它没有真的撤销之前所有决策但通过替换不断修正局部最优最终达到全局最优。周赛里更复杂的反悔贪心比如用优先队列维护一组候选当遇到一个更优方案时把队列里最差的元素弹出。这个思路和 LIS 贪心在精神上是同构的维护一组“潜力最大的状态”并随时准备用更好的替换它。所以我建议你把 LIS 贪心解法理解透而不是只背代码。当你真的理解的替换操作后面遇到很多“维护当前最优集合”的题目都会觉得眼熟。在我自己的刷题习惯里这道题最少要写三遍第一遍用动态规划把状态转移和边界条件搞清楚第二遍用贪心加二分重点理解tails数组的含义并且用随机数据交叉验证两种解法的结果第三遍对着白板讲给别人听能讲清楚为什么tails不能直接当子序列输出才算是真正过关。最长递增子序列就是这样一道题代码可能不超过十行但背后的状态设计、贪心选择、二分边界每一层都值得你慢慢拆开看。