1. 项目概述从一道国赛真题看算法思维的锤炼“递增序列”这四个字对于参加过蓝桥杯这类算法竞赛的同学来说绝对是一个能瞬间激起复杂回忆的关键词。它不像“动态规划”那样自带光环也不像“图论”那样结构复杂但它恰恰是检验一个程序员基础算法思维和代码实现能力的绝佳试金石。我至今还记得第一次在模拟赛中遇到类似题目时那种看似简单、实则处处是坑的感觉。题目要求往往很直接给定一个数字序列找出其中最长的严格递增子序列的长度。但当你真正动手去实现时才会发现从最朴素的暴力搜索到经典的动态规划解法再到更优的贪心加二分查找这中间每一步的跨越都代表着对问题理解深度的不同层次。这道题之所以能成为第十届蓝桥杯国赛JAVA B组的题目其价值远不止于求解一个具体案例。它考察的核心是选手在面对一个经典问题时能否清晰地分析时间复杂度能否在有限的内存和时间内选择最优策略以及能否用严谨的Java代码将思路无差错地实现出来。对于正在备战竞赛或者准备面试的同学而言深入吃透“最长递增子序列”Longest Increasing Subsequence, LIS问题就等于掌握了一把打开许多中高级算法面试题的钥匙。今天我就结合这道国赛真题把自己在刷题和教学中总结的思路、代码细节以及避坑经验系统地梳理一遍希望能帮你不仅“做出”这道题更能“吃透”它背后的算法逻辑。2. 核心思路解析从暴力枚举到最优解的思维跃迁面对“递增序列”问题我们的第一反应往往是穷举。这种最直观的思路恰恰是理解问题本质的起点。2.1 暴力搜索DFS的思路与局限性最原始的想法是深度优先搜索DFS对于序列中的每一个元素我们都有“选”或“不选”两种选择目标是找到所有选择的组合中能构成严格递增序列的最长长度。例如对于序列[10, 9, 2, 5, 3, 7, 101, 18]我们可以从10开始尝试选择下一个比10大的数如果没有则回溯。这种方法的思路非常直接代码上也相对好理解。为什么我们最终会放弃这种思路核心原因在于时间复杂度。对于一个长度为n的序列每个元素有选或不选两种状态那么所有可能的子序列数量是2^n量级。当n达到20时操作次数就超过百万n为30时将超过十亿。在竞赛或面试场景下n动辄上千甚至上万O(2^n)的复杂度是完全不可接受的。这迫使我们必须寻找更聪明的办法。2.2 动态规划DP解法的引入与状态定义动态规划是解决此类“最优化”问题的利器。它的核心思想是“记住过去避免重复计算”。对于LIS问题一个经典且必须掌握的DP定义如下我们定义dp[i]表示以第i个数字结尾的所有递增子序列中最长的那个子序列的长度。注意这个定义的关键词“以...结尾”。这意味着dp[i]的值完全由它之前的、且比它小的那些元素的状态决定。状态转移方程也就呼之欲出了为了计算dp[i]我们需要遍历i之前的所有位置j(0 j i)。如果nums[j] nums[i]说明nums[i]可以接在nums[j]结尾的子序列后面形成一个更长的递增子序列。那么dp[i]至少可以是dp[j] 1。我们要做的就是对所有满足条件的j取dp[j] 1的最大值。状态转移方程dp[i] max(dp[j] 1), 对于所有0 j i且nums[j] nums[i]。 如果不存在这样的j即nums[i]是前i1个数里的最小值那么dp[i] 1子序列只包含它自己。整个序列的最长递增子序列长度就是dp数组中的最大值max(dp[0], dp[1], ..., dp[n-1])。这个解法的时间复杂度是 O(n²)空间复杂度是 O(n)。对于n在10^4量级以内的题目这个解法通常是够用的也是面试中面试官期望你至少能写出来的解法。它清晰地展示了如何将一个大问题分解为重叠的子问题并用数组存储子问题的解。2.3 贪心二分查找的优化思路当n进一步增大到10^5甚至10^6时O(n²) 的DP解法也会超时。这时就需要更优的O(n log n)解法。这个解法的思想非常巧妙它并不直接求出以每个元素结尾的LIS长度而是维护一个“潜在的增长序列”。我们维护一个数组tail或者叫d。tail[i]的定义是所有长度为i1的递增子序列中结尾元素的最小值。这个定义是理解整个算法的关键。为什么维护“最小结尾元素”因为对于相同长度的递增子序列结尾元素越小未来才有更大的可能接纳新的元素从而使序列变得更长。这是一种典型的贪心思想。算法流程如下初始化tail为空数组。遍历原序列nums中的每一个数x。在tail数组中寻找第一个大于等于x的数。如果找不到即x比tail中所有数都大说明x可以接在当前最长的子序列后面形成更长的序列。将x添加到tail末尾。如果找到了假设位置为i那么用x替换tail[i]。因为x比原来的tail[i]更小以x作为长度为i1的子序列的结尾“潜力”更大。注意这个算法最终得到的tail数组的长度就是最长递增子序列的长度。但是tail数组本身并不一定是一个合法的LIS它只是维护了每个长度下的最小结尾这些结尾可能来自原序列中不同的位置无法直接连成一个子序列。如果题目要求输出具体的序列则需要配合额外的数组来记录路径。这里的“寻找第一个大于等于x的数”正是二分查找Binary Search的用武之地。因为在整个过程中tail数组本身是严格递增的可以通过反证法证明这为二分查找提供了前提条件。这使得整个算法的时间复杂度降为O(n log n)。关键理解点O(n²)的DP是“我以谁结尾”而O(n log n)的贪心是“多长的序列目前最小结尾是谁”。后者跳过了对每个i都要遍历前面所有j的过程通过维护一个有序数组用二分快速定位更新位置实现了降维打击。3. 代码实现与细节剖析理论清晰之后我们来看代码实现。这里我提供Java版本的两种解法并会逐行分析关键细节和易错点。3.1 O(n²) 动态规划解法实现public class LIS_DP { public int lengthOfLIS(int[] nums) { if (nums null || nums.length 0) { return 0; } int n nums.length; // dp[i] 表示以 nums[i] 结尾的最长递增子序列长度 int[] dp new int[n]; // 初始化每个元素本身至少可以构成长度为1的子序列 Arrays.fill(dp, 1); int maxLen 1; // 全局最大长度至少为1 for (int i 1; i n; i) { // 遍历 i 之前的所有元素 for (int j 0; j i; j) { // 严格递增必须 nums[j] nums[i] if (nums[j] nums[i]) { // 状态转移尝试用 nums[j] 结尾的序列接上 nums[i] dp[i] Math.max(dp[i], dp[j] 1); } } // 更新全局最大值 maxLen Math.max(maxLen, dp[i]); } return maxLen; } }代码细节与避坑指南边界条件处理首先判断输入数组是否为空这是写出健壮代码的第一步。如果数组为空最长递增子序列长度自然是0。dp数组初始化Arrays.fill(dp, 1)是关键。因为每个元素自身就是一个长度为1的递增子序列。很多初学者会忘记初始化导致结果错误。循环起始外层循环i从1开始因为dp[0]已经确定是1不需要再计算。内层循环j从0遍历到i-1。严格递增判断条件是nums[j] nums[i]注意是严格小于。如果题目要求是“非递减”即允许相等则需要改为nums[j] nums[i]。这是题目常见的变体务必看清题意。最大值更新最大值可能在dp数组的任意位置所以需要在每次更新dp[i]后同步更新maxLen。也可以在最后再遍历一次dp数组找最大值但这样多了一次循环。3.2 O(n log n) 贪心二分查找解法实现public class LIS_GreedyBinarySearch { public int lengthOfLIS(int[] nums) { if (nums null || nums.length 0) { return 0; } int n nums.length; // tail 数组tail[i] 表示长度为 i1 的递增子序列的最小结尾元素 int[] tail new int[n]; // len 记录当前 tail 数组的有效长度即当前找到的LIS长度 int len 0; tail[len] nums[0]; // 初始化第一个元素直接放入 for (int i 1; i n; i) { int x nums[i]; // 情况1如果 x 大于 tail 数组的最后一个元素即当前最大结尾 if (x tail[len - 1]) { tail[len] x; // 延长序列 } else { // 情况2在 tail[0...len-1] 中寻找第一个大于等于 x 的位置将其替换为 x // 使用二分查找提高效率 int left 0, right len - 1; while (left right) { int mid left (right - left) / 2; // 防止溢出 if (tail[mid] x) { right mid; // 目标在左半部分含mid } else { left mid 1; // 目标在右半部分 } } // 循环结束left 即为要替换的位置 tail[left] x; } } // tail 数组的有效长度 len 即为 LIS 的长度 return len; } }代码细节与避坑指南tail数组的含义再强调tail[i]存储的是长度为i1的所有递增子序列中结尾数字最小的那个值。它本身不一定是一个子序列但其长度len就是答案。二分查找的写法这是极易出错的地方。我们查找的是第一个大于等于x的元素的位置即Java中Arrays.binarySearch如果没找到返回的插入点。循环条件while (left right)在tail[mid] x时right mid因为mid可能就是我们要找的位置否则left mid 1。最终left和right会指向同一个位置即目标下标。防止整数溢出计算中点时使用left (right - left) / 2而非(left right) / 2这是一个良好的编程习惯可以避免left right可能导致的整数溢出问题。初始化先将第一个元素放入tail并设置len 1。条件判断顺序先判断x tail[len-1]是否成立。如果成立直接追加这是最简单的情况。如果不成立再进行二分查找替换。这个顺序让逻辑更清晰。3.3 两种解法的对比与选择特性O(n²) 动态规划解法O(n log n) 贪心二分解法时间复杂度O(n²)O(n log n)空间复杂度O(n)O(n)核心思想状态转移记录以每个元素结尾的LIS长度贪心维护每个长度下的最小结尾二分定位能否求出具体序列可以需额外记录前驱指针不能直接得到需配合pos数组记录索引来重构代码复杂度简单直观双重循环中等需正确实现二分查找适用场景n ≤ 10⁴ 的常规题目面试基础考察n ≥ 10⁵ 的大数据量题目竞赛或面试进阶考察选择建议面试场景如果面试官没有特别说明先给出DP解法并分析其复杂度是稳妥的选择。如果面试官追问“有没有更优解”再引出贪心二分解法并阐述其思想。这展示了你的思维层次。竞赛场景直接使用O(n log n)解法因为竞赛题的数据规模通常设计为卡掉O(n²)的解法。在线判题OJ根据题目给定的数据范围n来选择。如果n ≤ 5000DP可能也能过如果n ≤ 10^5则必须使用贪心二分。4. 常见变体与问题扩展“递增序列”问题绝非一成不变掌握其核心后可以应对多种变体这也是面试和竞赛中常见的套路。4.1 变体一输出具体的递增子序列这是最常见的变体要求。对于O(n²)的DP解法修改起来相对直接。思路在计算dp[i]的同时用一个pre[i]数组记录状态转移的路径即“以nums[i]结尾的最长递增子序列”的前一个元素的下标。最后我们先找到dp数组中最大值对应的下标maxIndex然后通过pre数组向前回溯即可得到逆序的序列最后反转即可。public ListInteger getLIS(int[] nums) { int n nums.length; int[] dp new int[n]; int[] pre new int[n]; // 记录前驱索引-1表示无前驱 Arrays.fill(dp, 1); Arrays.fill(pre, -1); int maxLen 1, maxIndex 0; for (int i 0; i n; i) { for (int j 0; j i; j) { if (nums[j] nums[i] dp[j] 1 dp[i]) { dp[i] dp[j] 1; pre[i] j; // 记录是从 j 转移过来的 } } if (dp[i] maxLen) { maxLen dp[i]; maxIndex i; } } // 回溯构造序列 ListInteger lis new ArrayList(); int cur maxIndex; while (cur ! -1) { lis.add(nums[cur]); cur pre[cur]; } Collections.reverse(lis); // 回溯得到的是逆序需要反转 return lis; }对于O(n log n)的解法要输出具体序列就复杂一些。我们需要在更新tail数组时额外维护一个pos数组记录原序列中每个元素在tail数组中出现时的位置即它作为多长的子序列的结尾。同时维护一个pre数组。在最后我们从tail数组的最后一个有效位置即LIS的最后一个元素在原序列中对应的、且能使得序列最长的那个位置开始回溯。这种方法实现起来更绕在面试中如果要求输出序列通常期望的是DP解法。4.2 变体二最长非递减子序列这是条件放宽的变体允许子序列中的元素相等。修改非常简单只需要在判断条件上把改为即可。对于DP解法将内层循环的判断条件if (nums[j] nums[i])改为if (nums[j] nums[i])。对于贪心二分解法将二分查找的条件从“查找第一个大于等于x的位置”改为“查找第一个大于x的位置”。因为对于非递减序列如果tail中已经有一个等于x的元素我们不应该替换它替换了还是等于x没有优化潜力只有当遇到比x大的元素时才用x去替换它以保证“最小结尾”的性质。实际上代码中只需将if (tail[mid] x)改为if (tail[mid] x)。4.3 变体三二维“递增”问题如俄罗斯套娃信封问题这是一个著名的LeetCode难题354. 俄罗斯套娃信封问题。问题描述给定一些信封的宽度和高度对(w, h)如果一个信封的宽度和高度都大于另一个信封则小的可以套进大的。求最多能套多少层。解题思路此问题可以巧妙地转化为一维LIS问题。排序首先将所有信封按宽度w升序排序。这样在宽度维度上已经满足了“递增”的条件。处理宽度相同的情况这是一个关键技巧。当宽度相同时我们必须按高度h降序排序。为什么因为宽度相同的信封无法互相嵌套宽度不满足严格大于。如果我们对高度也升序排序那么在寻找高度LIS时可能会错误地将宽度相同但高度递增的信封算进去。而降序排序保证了在宽度相同的信封中最多只会选取一个因为高度是递减的无法形成严格递增序列从而避免了宽度相同的干扰。转化为LIS排序后忽略宽度维度只关注高度数组h[]。在这个高度数组上求严格最长递增子序列的长度即为答案。因为排序后宽度已经非递减我们只需要保证高度严格递增就能满足信封嵌套的“两个维度都严格大于”的条件。public int maxEnvelopes(int[][] envelopes) { if (envelopes null || envelopes.length 0) return 0; // 排序宽度升序宽度相同时高度降序 Arrays.sort(envelopes, (a, b) - a[0] b[0] ? b[1] - a[1] : a[0] - b[0]); // 提取高度数组 int[] heights new int[envelopes.length]; for (int i 0; i envelopes.length; i) { heights[i] envelopes[i][1]; } // 在高度数组上求LIS严格递增 return lengthOfLIS(heights); // 调用之前的 O(n log n) 方法 }这个变体完美展示了如何通过巧妙的预处理将复杂的二维问题降维到熟悉的一维LIS模型是算法思维的一个精彩应用。5. 实战调试与性能分析理论代码写完了但在实际运行尤其是在竞赛环境中还需要考虑一些实际问题。5.1 如何验证代码正确性不要只依赖题目给的样例。自己构造测试用例边界用例空数组[]单元素数组[1]完全递减数组[5,4,3,2,1]答案应为1完全递增数组[1,2,3,4,5]答案应为5。常规用例[10,9,2,5,3,7,101,18]经典例子答案4。包含重复元素的用例[2,2,2,2]严格递增答案为1非递减答案为4。随机大数组用程序生成一个长数组用O(n²)的DP解法确保逻辑正确和O(n log n)的解法对比结果确保优化算法正确。5.2 时间复杂度与空间复杂度分析O(n²) DP两层循环内存操作简单。当 n10000 时循环次数约1亿次在现代CPU上尚可在1秒内完成C可能更稳Java稍慢。n20000时操作次数达4亿很可能超时时间限制通常1-2秒。O(n log n) 贪心二分一层循环加二分查找。n10^5时循环10万次每次二分查找约17次log2(100000)≈17总操作约170万次非常快。n10^6时也游刃有余。在蓝桥杯等竞赛中Java本身比C慢因此对时间复杂度的要求更为苛刻。看到数据范围n 1000可以放心用DP看到n 100000必须用贪心二分。5.3 内存与输入输出优化对于Java选手在处理极大输入时比如 n10^5有两点需要注意输入效率避免使用Scanner它虽然方便但较慢。使用BufferedReader会快很多。BufferedReader br new BufferedReader(new InputStreamReader(System.in)); String[] firstLine br.readLine().split( ); int n Integer.parseInt(firstLine[0]); int[] nums new int[n]; String[] numStrs br.readLine().split( ); for (int i 0; i n; i) { nums[i] Integer.parseInt(numStrs[i]); }输出效率大量输出时使用StringBuilder拼接结果最后一次性输出比多次调用System.out.println快。StringBuilder sb new StringBuilder(); sb.append(result).append(\n); System.out.print(sb.toString());5.4 常见“坑点”与错误排查初始化错误DP解法中忘记将dp数组初始化为1导致所有结果都偏小。二分查找死循环或错误在实现O(n log n)解法时二分查找的边界条件 (while (left right)还是while (left right)) 和更新逻辑 (right mid还是right mid - 1) 极易写错。务必用[2,5,3,4,1]这样的小例子手动模拟确保每一步都正确。题意理解偏差最致命的是没看清是“严格递增”还是“非递减”。一字之差代码的判断条件完全不同。更新全局最大值的时机在DP的双重循环中更新maxLen应该放在内层循环之后即确定dp[i]的最终值之后。放在内层循环里面会导致错误。贪心解法中tail数组的含义混淆误以为tail就是最终的子序列试图直接输出它。实际上它只是辅助数组其长度才是答案。6. 从解题到思维LIS问题的本质与启发刷完一道题更重要的是提炼其中的思维模式。LIS问题给我们哪些启示1. 定义状态是动态规划的灵魂。dp[i]定义为“以 i 结尾”而不是“前 i 个元素中”是这个解法能够成立的关键。这种“结尾限定”的状态定义在很多序列DP问题中都很常见如最大子数组和。它确保了状态的无后效性——当前状态只与之前的具体状态有关而与如何达到那个状态无关。2. 贪心策略的证明是难点但思想直观。O(n log n)解法中的贪心策略维护最小结尾并不容易严格证明但其思想非常符合直觉为了让序列更长我们希望已经构建的序列的结尾尽可能小这样后面才有更多机会接上新的数。在竞赛中我们有时不需要完全理解证明但必须深刻理解其正确性和操作流程。3. 二分查找的引入是优化复杂度的常见手段。当我们需要在一个有序集合中频繁进行“查找”和“更新”操作时二分查找能将线性查找的O(n)优化为O(log n)。这与在排序数组中找插入位置是同一类问题。4. 掌握经典问题是为了解决新问题。就像俄罗斯套娃信封问题表面上是一个二维排序问题但通过巧妙的排序规则成功转化为了LIS问题。这种“转化”或“建模”的能力是解决复杂算法问题的核心。当你遇到一个新的最优化序列问题时不妨想想它能不能排序排序后能不能转化为已知的模型如LIS、LCS回过头看蓝桥杯的这道国赛题它考察的绝不仅仅是背下一个模板。它考察的是选手能否在压力下清晰地分析问题边界选择合适的数据结构和算法并写出正确、高效的代码。从暴力搜索的思考到动态规划的状态设计再到贪心二分的优化这一整套思维链条正是算法学习中最有价值的部分。