1. 项目概述从一道经典算法题看“递增序列”的解题艺术最近在整理历年蓝桥杯国赛的真题2019年这道“递增序列”的题目又一次吸引了我的注意。它不像那些复杂的图论或动态规划问题一样有着炫目的技巧但恰恰是这种看似基础的问题最能考验一个程序员对问题本质的理解、对数据结构的驾驭能力以及编写健壮、高效代码的基本功。很多朋友在初次接触时可能会觉得“不就是找递增的子序列吗”但实际动手后才发现里面藏着对“序列”操作的深刻理解以及对时间、空间复杂度平衡的精准把控。这道题可以说是检验你是否真正吃透了线性数据结构处理的绝佳试金石。简单来说题目会给定一个整数序列我们需要从中找出最长的严格递增子序列Longest Increasing Subsequence, LIS。注意这里的子序列不要求连续只要保持原序列中的相对顺序即可。例如对于序列[2, 1, 5, 3, 6, 4, 8, 9, 7]最长的递增子序列之一是[1, 3, 4, 8, 9]长度为5。解决这个问题不仅是为了应对竞赛在现实开发中诸如股票趋势分析、数据流中的有序事件匹配、版本历史比对等场景其核心逻辑都与此高度相关。接下来我将结合自己多次解题和教学的经验彻底拆解这道题从最朴素的暴力搜索到经典的动态规划再到效率极高的贪心二分查找优化并分享在编码实现中那些容易踩坑的细节。2. 问题核心与思路演进为什么LIS问题值得深究2.1 问题定义与输入输出规范首先我们必须明确题目的精确要求。在蓝桥杯的赛场环境下任何对题意的误读都是致命的。典型的题目描述会如下给定一个长度为 N 的整数序列 A找出它的最长严格递增子序列的长度。这里有几个关键点需要敲黑板严格递增这意味着子序列中相邻的两个元素必须满足A[i] A[j](i j)。相等是不允许的。子序列元素可以不连续。这是与“子数组”或“连续子序列”最根本的区别。正是这个特性使得我们不能用简单的滑动窗口来解决。输出通常只需要输出最长递增子序列的长度。有些变体题目会要求输出具体的序列但2019年国赛题以输出长度为主我们首先聚焦于此。输入格式一般是第一行一个整数 N第二行 N 个用空格隔开的整数代表序列 A。数据范围往往是 N 最大为 1000 甚至 10000这就要求我们的算法必须在 O(N²) 或更优的时间复杂度内完成。2.2 从暴力枚举到动态规划的思想跃迁最直接的想法是暴力枚举所有可能的子序列检查其是否递增并记录最大长度。一个长度为 N 的序列其子序列总数高达 2^N 个这显然是不可接受的。我们需要更聪明的办法。动态规划DP是解决此类“最优子结构”问题的利器。其核心思想是定义状态并找到状态之间的转移关系。对于 LIS 问题一个最自然的状态定义是dp[i]表示以第i个数字即A[i]结尾的最长递增子序列的长度。为什么这么定义因为“以某个元素结尾”是一个清晰的边界方便我们进行状态转移。思考一下如何得到dp[i]要想让A[i]能接在一个递增子序列的后面那么这个子序列的最后一个元素即A[i]的前一个元素必须小于A[i]。并且我们应该接在能形成最长序列的那个元素后面。因此状态转移方程就呼之欲出了dp[i] max(dp[j]) 1 其中0 j i且A[j] A[i]。这个方程的含义是对于每个位置i我遍历它之前的所有位置j如果A[j]比A[i]小那么A[i]就可以接在以 A[j] 结尾的 LIS后面形成一个更长的序列。我们只需要在所有可行的j中选择一个dp[j]最大的然后加1就得到了dp[i]。初始化时每个元素自身至少可以构成一个长度为1的序列所以dp[i] 1。 最终答案就是整个dp数组中的最大值max(dp[0], dp[1], ..., dp[N-1])。这个算法的时间复杂度是 O(N²)因为对于每个i我们都需要遍历一次它之前的所有j。空间复杂度是 O(N)。对于 N 在 10^4 量级的数据O(N²) 可能会达到 10^8 次操作在竞赛环境中处于临界状态有时需要进一步优化。注意这里有一个初学者极易混淆的点。dp[i]表示的是“以A[i]结尾”的LIS长度而不是“前 i 个元素中”的LIS长度。后者是一种不同的状态定义其转移会更复杂。当前这种定义是更直观和高效的。2.3 贪心与二分查找将复杂度优化到 O(N log N)当 N 很大时例如 10^5O(N²) 的 DP 就无法胜任了。这时就需要经典的“贪心 二分查找”算法将时间复杂度降至 O(N log N)。这个算法理解起来略有门槛但一旦掌握威力无穷。算法的核心是维护一个单调递增的数组tail。tail[i]的定义是所有长度为 i1 的递增子序列中末尾元素的最小值。这个定义非常巧妙。为什么记录“最小末尾元素”因为对于相同长度的递增子序列末尾元素越小未来“潜力”就越大越有可能接上后续更多的元素从而使序列变得更长。我们依次遍历原序列A中的每个元素x如果x比tail数组最后一个元素即当前最长子序列的末尾还要大说明我们可以得到一个更长的递增子序列。那么就把x追加到tail的末尾。否则我们在tail数组中寻找第一个大于等于x的元素并用x替换它。因为tail数组是单调递增的所以这个查找过程可以用二分查找在 O(log N) 时间内完成。这个“替换”操作是算法的精髓。它并没有改变tail数组的长度即当前找到的 LIS 长度但它让tail数组的每个位置存储了更小的、更有潜力的末尾元素为后续可能出现的更长序列做准备。遍历结束后tail数组的长度就是最长递增子序列的长度。让我们用之前的例子[2, 1, 5, 3, 6, 4, 8, 9, 7]走一遍流程初始tail []2:tail为空直接加入 -tail [2]1: 比2小二分查找替换tail[0]-tail [1](长度为1的子序列更好的末尾是1)5: 比1大追加 -tail [1, 5]3: 比5小二分查找替换tail[1](5) -tail [1, 3]6: 比3大追加 -tail [1, 3, 6]4: 比6小二分查找替换tail[2](6) -tail [1, 3, 4]8: 比4大追加 -tail [1, 3, 4, 8]9: 比8大追加 -tail [1, 3, 4, 8, 9]7: 比9小二分查找替换tail[4](9) -tail [1, 3, 4, 7, 9]最终tail长度为 5即 LIS 长度为 5。需要注意的是此时tail数组[1, 3, 4, 7, 9]并不一定是原序列中真实存在的一个 LIS原序列中7在9后面但它正确地记录了长度。如果需要还原具体的序列则需要额外的数组来记录路径信息。3. 代码实现与细节剖析理解了原理代码实现就是水到渠成。但魔鬼在细节中不同的实现方式在边界条件和效率上会有差异。3.1 O(N²) 动态规划标准实现def length_of_lis_dp(nums): 使用动态规划计算最长递增子序列长度。 时间复杂度 O(N²)空间复杂度 O(N)。 if not nums: return 0 n len(nums) # dp[i] 表示以 nums[i] 结尾的最长递增子序列长度 dp [1] * n # 初始化为1每个元素自身构成一个序列 # 计算每个位置的 dp 值 for i in range(n): for j in range(i): if nums[j] nums[i]: # 如果 nums[j] nums[i]则 nums[i] 可以接在 nums[j] 后面 dp[i] max(dp[i], dp[j] 1) # 最终结果是 dp 数组中的最大值 return max(dp) # 测试用例 if __name__ __main__: test_nums [2, 1, 5, 3, 6, 4, 8, 9, 7] print(f序列: {test_nums}) print(fDP方法 LIS 长度: {length_of_lis_dp(test_nums)}) # 输出 5实操要点与避坑指南初始化dp数组必须初始化为1。我曾见过有初学者初始化为0导致结果永远比正确值少1。内层循环范围for j in range(i)确保了j严格在i之前。这是正确的。状态转移条件必须是nums[j] nums[i]严格递增。如果是非递减即允许相等条件应改为nums[j] nums[i]。取最大值dp[i] max(dp[i], dp[j] 1)这里dp[i]可能被多个j更新我们要取最大值。最终答案不是dp[-1]必须以max(dp)作为答案因为最长序列不一定以最后一个元素结尾。3.2 O(N log N) 贪心二分查找优化实现import bisect def length_of_lis_greedy(nums): 使用贪心 二分查找计算最长递增子序列长度。 时间复杂度 O(N log N)空间复杂度 O(N)。 if not nums: return 0 tail [] # tail[i] 定义为长度为 i1 的递增子序列的最小末尾值 for num in nums: # 使用二分查找在 tail 中找到第一个 num 的位置 pos bisect.bisect_left(tail, num) if pos len(tail): # 如果 num 大于所有 tail 中的元素可以延长当前最长序列 tail.append(num) else: # 否则用 num 替换掉那个位置上的元素使其保持最小 tail[pos] num # tail 的长度即为 LIS 的长度 return len(tail) # 手动实现二分查找的版本 def length_of_lis_greedy_manual(nums): 手动实现二分查找便于理解过程 tail [] for num in nums: left, right 0, len(tail) # 二分查找左边界第一个 num 的位置 while left right: mid left (right - left) // 2 if tail[mid] num: left mid 1 else: right mid if left len(tail): tail.append(num) else: tail[left] num return len(tail) # 测试 if __name__ __main__: test_nums [2, 1, 5, 3, 6, 4, 8, 9, 7] print(f序列: {test_nums}) print(f贪心二分 (bisect) LIS 长度: {length_of_lis_greedy(test_nums)}) # 输出 5 print(f贪心二分 (手动) LIS 长度: {length_of_lis_greedy_manual(test_nums)}) # 输出 5关键细节与深度解析为什么用bisect_left而不是bisect_right这是核心。bisect_left返回的是第一个大于等于num的位置。我们的目标是找到tail中第一个不小于num的数并将其替换。如果使用bisect_right返回第一个大于num的位置当tail中存在与num相等的值时替换逻辑会出错可能破坏序列的严格递增性。bisect_left保证了替换行为的正确性维持了tail数组的单调性。tail数组的性质在整个过程中tail数组始终保持严格单调递增。这是二分查找能够应用的前提也是算法正确性的基石。空间复杂度虽然我们维护了一个tail数组但其最大长度不会超过 N因此空间复杂度是 O(N)。在实际内存占用上它和 DP 方法的dp数组是同一量级。还原具体序列上述算法只返回长度。如果需要输出一个具体的 LIS我们需要额外维护一个parent数组。在 DP 方法中这很容易在更新dp[i]时记录前驱j即可。在贪心算法中还原序列稍微复杂一些需要同时维护tail数组和每个元素在tail中的位置索引最后从后向前重构。这在竞赛中属于进阶要求。4. 算法对比与场景选择在实际编码尤其是竞赛中我们该如何选择呢这里我总结了一个对比表格方便大家根据实际情况决策特性O(N²) 动态规划 (DP)O(N log N) 贪心二分 (Greedy)时间复杂度O(N²)O(N log N)空间复杂度O(N)O(N)编码难度简单直观易于理解和实现中等需要理解tail数组的抽象定义和二分查找的边界额外功能易于还原具体序列。在状态转移时记录前驱即可。仅直接得到长度。还原具体序列需要额外记录信息逻辑稍复杂。适用数据规模N ≤ 10⁴ 通常可接受10^8 操作量级N 可达 10⁵ 甚至 10⁶思维核心穷举所有可能的前驱状态取最优。维护潜在的最优末尾序列贪心地让未来有更多可能。我的经验选择在蓝桥杯等竞赛中如果题目明确 N ≤ 1000我会毫不犹豫使用 DP 方法。因为它编码快不易出错且万一题目变体要求输出序列DP 方法修改起来极其方便。时间完全够用。如果 N 可能很大或者在做题平台看到 N 上限是 10^5那么必须使用贪心二分法。这是区分能否拿到满分的关键。在面试或工程中优先阐述 O(N log N) 的方法因为它体现了对算法效率的追求。如果面试官追问如何输出序列再基于 DP 方法进行讨论。一个重要的心得很多同学在学会贪心二分法后就抛弃了 DP 方法。但我建议两者都要熟练掌握。DP 方法是基础其“以某个位置结尾”的状态定义思想是解决许多其他子序列问题如最长公共子序列、最大子数组和等的通用钥匙。贪心二分则是特定条件下的高效优化理解其为何能优化比单纯记住代码更重要。5. 变体问题与扩展思考“递增序列”问题本身就有很多变体掌握核心解法后可以轻松应对。5.1 变体一非严格递增不下降子序列这是最常见的变体即允许子序列中相邻元素相等。修改非常简单DP 方法将状态转移条件从nums[j] nums[i]改为nums[j] nums[i]。贪心二分方法将二分查找的bisect_left改为bisect_right。因为tail数组现在允许存储相等的值我们要找到第一个大于num的位置进行替换以维持数组的非严格递增性。5.2 变体二输出一个具体的最长递增子序列如前所述DP 方法更容易实现这个功能。我们需要一个额外的prev数组在更新dp[i]时记录使得dp[i]取得最大值的那个前驱索引j。最后从dp值最大的位置开始根据prev数组向前回溯即可得到逆序的序列再反转即可。def lis_with_sequence_dp(nums): 使用DP方法返回长度和一个具体的LIS if not nums: return 0, [] n len(nums) dp [1] * n prev [-1] * n # 记录前驱索引-1表示无前驱 max_len 1 max_idx 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] max_len: max_len dp[i] max_idx i # 回溯构造序列 sequence [] cur max_idx while cur ! -1: sequence.append(nums[cur]) cur prev[cur] sequence.reverse() # 回溯得到的是逆序需要反转 return max_len, sequence # 测试 test_nums [2, 1, 5, 3, 6, 4, 8, 9, 7] length, seq lis_with_sequence_dp(test_nums) print(fDP方法找到的LIS长度: {length}, 一个具体序列: {seq}) # 可能是 [1, 3, 4, 8, 9] 或 [1, 3, 4, 7, 9] 等5.3 变体三二维“递增”问题如“俄罗斯套娃信封”这是一个著名的LeetCode难题354. 俄罗斯套娃信封问题。问题描述为给定一些信封的宽度和高度当另一个信封的宽度和高度都大于某个信封时可以套进去。问最多能套多少层。这本质上是一个二维的 LIS 问题。一个巧妙的解法是先将信封按宽度升序排序。这样我们只需要关注高度的递增关系。但是当宽度相同时必须按高度降序排序。这是关键为什么因为宽度相同的信封是不能互相套的宽度不严格大于。如果我们对高度也升序排序在寻找高度LIS时可能会把宽度相同但高度不同的信封算进去导致错误。将高度降序排序就保证了在宽度相同的信封中最多只会选取一个因为高度是递减的无法形成递增序列。排序后忽略宽度直接在高度数组上求 LIS 的长度即为答案。def max_envelopes(envelopes): :type envelopes: List[List[int]] :rtype: int if not envelopes: return 0 # 关键排序宽度升序宽度相同时高度降序 envelopes.sort(keylambda x: (x[0], -x[1])) # 提取高度数组并在其上求LIS heights [h for _, h in envelopes] return length_of_lis_greedy(heights) # 使用 O(N log N) 的方法这个变体完美展示了如何将复杂问题转化为已知的 LIS 模型其中排序的技巧是解题的关键。6. 调试技巧与常见“坑点”实录即便理解了算法在实现时依然可能遇到各种问题。下面是我和学生们在实战中踩过的一些坑坑点1二分查找的边界错误在手动实现贪心算法的二分查找时while left right和while left right的选择以及left mid 1和right mid - 1的更新很容易写错。我的建议是固定使用一种二分查找模板。上面代码中while left right配合right mid和left mid 1的写法是寻找左边界的经典模板不易出错。或者直接使用语言内置的bisect库更为稳妥。坑点2初始化与最终答案获取在 DP 方法中忘记将dp数组初始化为1或者错误地将答案认为是dp[-1]。务必记住每个元素自身就是长度为1的序列答案需要遍历dp数组取最大值。坑点3序列还原时的索引混乱当需要还原序列时prev数组记录的是前驱元素的索引而不是值。回溯结束时得到的是逆序序列需要反转。我建议在写这类代码时先用一个小例子在纸上画一下dp和prev数组的变化过程理清指针的走向。坑点4误判数据范围与算法选择这是竞赛中最致命的错误。看到题目就想当然用 O(N²) 的 DP提交后因为超时只得部分分数。养成好习惯在动手前先评估数据范围。如果 N 在 10^5 级别就必须考虑 O(N log N) 的解法。蓝桥杯有时不会明确给出 N 的最大值但可以通过内存和时间限制反推。调试建议从小样例开始不要一上来就用复杂用例。先用题目给的样例或者自己构造[1],[1,2,3],[3,2,1]这样的边界用例测试。打印中间变量对于 DP可以打印出每一步计算后的dp数组。对于贪心算法打印每一步更新后的tail数组。这能帮你最直观地看到算法是否按预期工作。对比两种方法如果你的 DP 方法和贪心方法对同一个输入得到了不同结果那一定是其中一个有 bug。用中等规模的随机数据比如 N20让两种方法都跑一遍对比结果能快速定位问题所在。回顾这道“递增序列”问题它的价值远不止于解出一道竞赛题。它像一把钥匙打开了理解动态规划状态设计、贪心策略优化以及二分查找应用的大门。在实际工作中这种寻找“最长有序子结构”的思想无处不在。我个人的体会是算法学习的精髓不在于背诵多少模板而在于像这样把一道经典题目吃透、拆解看清它从暴力到优化、从一维到二维的完整思考链条。下次当你遇到类似“最长”、“递增”、“子序列”这样的关键词时希望你能立刻回想起这篇文章里讨论的种种细节从容地选择最合适的方法干净利落地解决问题。