到O(nlogn)的优化)
刷题刷到动态规划这一块的时候最长递增子序列Longest Increasing SubsequenceLIS几乎是绕不开的一道题。我印象太深了某次面试里被问到“怎么在O(nlogn)时间内求LIS长度”我第一反应就是“n平方的dp不香吗”结果对面一句话把我问住了“如果n是10万呢”当场卡壳回去把这题翻来覆去研究了整整两天才发现这里面的门道比想象中深得多。这篇内容就是围绕“算法Day09-动态规划之最长递增子序列”这个主题展开的。我会把从暴力递归到O(n²)动态规划再到O(nlogn)贪心二分的完整演进路径讲清楚包括状态定义为什么这么写、二分法到底在二分什么、以及最容易被忽视的“如何还原真实递增子序列”这个问题。无论你是刚开始接触动态规划的入门选手还是刷题到中期想搞懂优化原理的进阶玩家这篇内容应该都能给你一些启发。1. 先把问题本身看得透透的1.1 问题定义里的两个陷阱在动手写代码之前我建议先把问题定义一个字一个字地抠清楚。什么是最长递增子序列给定一个数组比如[10,9,2,5,3,7,101,18]要求找到一个最长的子序列满足两个条件第一子序列不要求连续。这一点和子数组subarray有本质区别。子数组必须是原数组中连续的一段而子序列只是保持元素在原数组中的相对顺序中间可以跳元素。比如上面数组里[2,3,7,101]就是一个合法的子序列它们在原数组中的下标是2、4、5、6中间跳过了5和3完全没问题。正因为不连续这个特性才会引出后面那一堆动态规划的状态设计如果要求连续那直接用滑动窗口就能解决就谈不上什么“最长递增子序列”了。第二递增是严格递增还是非递减。这是面试里极其常见的变体稍不留神就会写错。严格递增意味着后一个元素必须大于前一个元素也就是nums[j] nums[i]相等的情况不能算数。但有些题会改成非递减那就变成了nums[j] nums[i]代码里的比较符号要改二分的策略也要相应调整。这个问题我后面专门开一节详细讲因为真的太多人在这里栽跟头。1.2 为什么暴力解法走不通理解了问题定义之后初学者最自然的想法是把所有递增子序列都枚举出来然后挑最长的。这在理论上是可行的但在实际中完全跑不动。一个长度为n的数组子序列的个数是2^n个就算剪枝掉大量非递增的情况最坏情况下枚举所有组合依然是指数级复杂度。当n20时2的20次方是1048576勉强能跑但n30时已经超过10亿了n50基本上就是天文数字。所以我们需要一个更聪明的办法。你会发现判断一个子序列是否递增其实只需要关注当前子序列的最后一个元素。也就是说状态转移只和“以某个元素结尾的递增子序列长度”有关之前具体选了哪些元素并不重要。这个“只需要记住当前最优状态、不需要记住过程细节”的思想正是动态规划能够把指数级问题降到多项式级复杂度的核心原因。用大白话说就是走一步看一步每次只需要根据前一步的最优结果来更新当前步子不需要回头把所有走过的路都重新走一遍来比较。1.3 动态规划的思考路径三个关键问题很多教程上来就直接甩状态定义和转移方程读者看得一头雾水。我觉得更重要的事情是建立一套思考路径面对任何动态规划题目先问自己三个问题第一个问题状态是什么在这个题目里“以某个位置为结尾的递增子序列的最大长度”是唯一需要维护的信息。这里的关键词是“以某个位置结尾”这是很多子序列类DP题目的惯用套路。第二个问题转移关系是什么如果我知道了所有在位置i之前且值小于nums[i]的元素j所对应的最优长度那么以i结尾的最长递增子序列长度就是这些dp[j]的最大值加1。这里体现的是最优子结构性质全局最优解可以由局部最优解组合而成。第三个问题边界条件是什么数组里任何一个单独的元素自身就是一个长度为1的递增子序列所以所有dp[i]初始化为1。想明白这三个问题O(n²)的解法就呼之欲出了。而O(nlogn)的解法则是在“转移关系”这一步做了优化用二分查找代替了线性扫描。下面我一步步来拆。2. O(n²)动态规划最直观的基线解2.1 状态定义与转移方程的由来我们定义dp[i]表示“以nums[i]这个元素结尾的最长递增子序列的长度”。这里特别要注意“以nums[i]结尾”意味着nums[i]必须被选入子序列并且是整个子序列的最后一个元素。这个限制非常关键它保证了我们在讨论dp[i]时有一个明确的归属点可以供后续转移使用。转移方程是dp[i] max(dp[i], dp[j] 1) 其中 0 j i 且 nums[j] nums[i]为什么这样转移因为如果nums[j] nums[i]那就意味着我可以把nums[i]接到以nums[j]结尾的那个递增子序列后面形成一个新的、长度加1的递增子序列。那么对于所有满足条件的j我找到一个能让我接上去之后长度最大的那个得到的就是dp[i]的最优值。举个例子数组[1,3,2,4]。dp[0]1因为只有1自己。i1时nums[1]3下标0的nums[0]1小于3所以dp[1]dp[0]12。i2时nums[2]2下标0的1小于2所以dp[2]dp[0]12下标1的3不小于2跳过。注意这里dp[2]并不能从dp[1]转移过来因为3不能接到2后面。i3时nums[3]4下标0的1、下标1的3、下标2的2都小于4分别对应dp[0]12、dp[1]13、dp[2]13取最大值得到dp[3]3。答案就是dp数组的最大值3对应子序列[1,2,4]或[1,3,4]。2.2 代码实现与边界处理代码写起来非常直接如果按照我前面说的状态定义来写就是两个for循环嵌套。注意外层是当前位置i内层扫描所有ji的位置。int lengthOfLIS(vectorint nums) { int n nums.size(); if (n 0) return 0; vectorint dp(n, 1); int ans 1; for (int i 0; i n; i) { for (int j 0; j i; j) { if (nums[j] nums[i]) { dp[i] max(dp[i], dp[j] 1); } } ans max(ans, dp[i]); } return ans; }有一个非常容易踩的细节ans应该初始化为1还是0如果数组为空直接返回0这是针对题目约束的空数组边界。如果数组非空那么至少有一个元素答案至少是1所以ans初始化为1没问题。但如果你的ans初始化为0并且数组只有一个元素那么内层循环不会执行ans会一直保持0最后返回0这就错了。虽然有些写法会在循环里处理但我个人习惯是先处理n0的case然后把ans初始化为1从i0开始正常循环。分情况讨论比依赖初始值更保险。2.3 复杂度分析与优化信号这个解法的时间复杂度是O(n²)空间复杂度是O(n)。外层循环n次内层循环最多n次总操作次数约等于n(n-1)/2也就是n²量级。当n10万时n²等于100亿这个量级在现代计算机上大概要跑几十秒到几分钟完全不符合大部分算法题的时限。所以问题就来了能不能把内层的线性扫描改成更快的方式我们可以拆解一下内层循环到底在做什么在已经扫描过的所有元素中找到所有值小于当前元素的那些位置取出其中dp值最大的一个。这里有两个维度一个是值的大小nums[j] nums[i]另一个是dp值的大小。有没有一种数据结构可以同时处理这两个维度这就是O(nlogn)解法的出发点。仔细想一想dp值有一个非常重要的单调性质如果nums[j] nums[k]且j k那么dp[j]最多等于dp[k]实际上通常dp[k] dp[j]因为以nums[k]结尾的序列长度至少不会比以nums[j]结尾的短只要nums[k]大于nums[j]的话可以直接接上。这个性质可以沿用到“用dp值分组”的思路。不过更优雅的解法其实是反过来思考不看dp值而是去看“长度为len的递增子序列它的最小末尾元素是多少”。这就是下一节的耐心排序思想。3. 进阶解法贪心二分O(nlogn)拿下3.1 从“维护最小末尾”开始理解先说结论。我们可以维护一个数组tails其中tails[i]表示“长度为i1的所有递增子序列中末尾元素的最小值”。这句话是理解整个O(nlogn)解法的钥匙我建议你多读几遍直到完全消化。这个tails数组有两个重要的性质性质一tails是严格递增的。证明很简单如果长度为i2的递增子序列末尾元素是x那么它去掉最后一个元素后剩下的是一个长度为i1的递增子序列其末尾元素必然小于x。所以长度为i2的递增子序列的最小末尾一定大于长度为i1的递增子序列的最小末尾。所以tails[i] tails[i1]恒成立。性质二tails的长度就是LIS的长度。因为tails数组中有多少个元素就说明存在长度为1、2、3……直到len的递增子序列所以最长递增子序列长度就是tails数组的size。有了性质一我们就可以对tails做二分查找了。这也是整个优化方案能够成立的关键tails有序所以查找可以用二分复杂度从线性降到对数级别。处理每个元素nums[i]的策略如下在tails中二分查找第一个大于等于nums[i]的位置pos。如果pos等于tails的长度说明nums[i]比tails里所有元素都大把它追加到尾部这代表我们找到了一个更长的递增子序列。否则用nums[i]替换掉tails[pos]。这个替换的意义是长度相同的递增子序列我们保留更小的末尾元素因为更小的末尾元素更有利于后续元素的拼接相当于“给未来留下更大的空间”。这就是经典的贪心策略的朴素解释很多人管它叫“耐心排序”Patience Sorting因为它在纸牌游戏里就是用来计算最少牌堆数的。3.2 为什么替换是正确的而不丢解初学者最容易质疑的一点是“用nums[i]替换tails[pos]会不会丢弃掉某些可能的更长序列”我们把问题想透。tails[pos]记录的是长度为pos1的递增子序列的最小末尾值。现在我们发现了一个新的长度为pos1的递增子序列其末尾值nums[i]更小也就是说这个新序列比原来记录的那个序列“更值得被延伸”。因为任何原本可以接在tails[pos]后面的元素一定可以接在nums[i]后面nums[i]比tails[pos]更小条件更宽松所以替换之后只会让未来更好不会让未来更差。而且注意替换操作并不会改变tails数组的最大长度也就是说它不会让你丢失已经求得的当前LIS长度。它做的是“同长度内部的优化”把每个长度的代表性值尽可能压小从而为后续更大的元素留出更长的接力跑道。这个思想你可以类比成你在找一个递增的长途队列队列越往后需要的人越“高”。如果前一个位置来了个更矮的人赶走原来的高个子让矮个子站这个位置后面再来的高个子反而更容易排进队伍里。整个过程不会让队伍变短只会让它有更多变长的机会。3.3 二分查找的正确写法代码如下我用的是C标准库的lower_bound它返回的是第一个大于等于目标值的迭代器。int lengthOfLIS(vectorint nums) { vectorint tails; for (int x : nums) { auto it lower_bound(tails.begin(), tails.end(), x); if (it tails.end()) { tails.push_back(x); } else { *it x; } } return tails.size(); }如果你不熟悉lower_bound可以看一下手写二分的版本int lengthOfLIS(vectorint nums) { vectorint tails; for (int x : nums) { int left 0, right tails.size(); while (left right) { int mid left (right - left) / 2; if (tails[mid] x) { left mid 1; } else { right mid; } } if (left tails.size()) { tails.push_back(x); } else { tails[left] x; } } return tails.size(); }注意我这里手写二分时left初始化为0right初始化为tails.size()这是一个“左闭右开”的区间。循环条件是left right最终left就是我们要找的位置。有不少人会在这里把边界写错最常见的是把right初始化成tails.size()-1然后用left right结果在空数组时直接越界。我的建议是统一用“左闭右开”这套模板不容易出错也方便记忆。3.4 复杂度对比与面试时的表述策略两种方法的时间、空间复杂度放在一起看非常清晰解法时间复杂度空间复杂度适用场景O(n²) DPO(n²)O(n)n 5000要求能还原子序列时O(nlogn) 贪心二分O(nlogn)O(n)n 10^4 的大规模数据在面试中我一般会先快速给出O(n²)的DP解法表示理解了问题的本质然后追问“如果数据量变大怎么办”再过渡到O(nlogn)解法。这两种解法一条主线讲下来面试官对你的印象分通常不会低。但这里必须指出一个非常关键的坑O(nlogn)的解法只回答了“长度是多少”如果要还原真实的递增子序列直接输出tails数组是错的这一点我见太多人踩了。举个例子数组[3,1,2,4]我们用tails过程推一下处理3tails变成[3]处理1替换3tails变成[1]处理2追加tails变成[1,2]处理4追加tails变成[1,2,4]。这里tails刚好等于真实LIS因为1本来是排在3后面的幸运地保持了下来。但如果数组是[1,3,2,4]处理1tails[1]处理3tails[1,3]处理2替换3tails[1,2]处理4tails[1,2,4]。这里tails是[1,2,4]和真实LIS一致因为2在3后面虽然替换了但数组顺序没毛病。再看[3,2,1,4]处理3tails[3]处理2替换3tails[2]处理1替换2tails[1]处理4tails[1,4]。真实LIS其实是[3,4]或者[2,4]或者[1,4]tails输出[1,4]虽然长度正确但也就罢了。最经典的坑是[10,9,2,5,3,7,101,18]tails最终是[2,3,7,18]但真实LIS可以是[2,5,7,101]或者[2,3,7,101]18根本不在正确答案里。因为18替换了101而101是在18后面出现的合法序列末尾替换操作导致了“覆盖”而不是“追加”tails数组里的值并不保证是真实子序列。那要还原真实子序列怎么办需要借助DP的思想辅助记录。在后面我会专门讲这个技巧。4. 从模板到实战变体情况与代码改造4.1 严格递增改非递减一个符号和一个二分边界的差别有相当多的题目会在LIS的基础上要求“非递减”而不是“严格递增”比如“最长不下降子序列”。改动点有两个第一个是O(n²) DP里的比较符号从nums[j] nums[i]改成nums[j] nums[i]。这很好理解允许相等元素的接续。第二个是O(nlogn)解法里的二分策略严格递增时我们要找的是第一个大于等于当前元素的位置用lower_bound非递减时如果当前元素等于tails里的某个值我们不能把它接到相等的元素后面因为如果允许相等那就可以直接接上所以我们需要找到第一个大于当前元素的位置也就是把“等于”也视为可追加的情况。在C里这个操作是upper_bound返回第一个大于目标值的迭代器。int lengthOfLISNonDecreasing(vectorint nums) { vectorint tails; for (int x : nums) { auto it upper_bound(tails.begin(), tails.end(), x); if (it tails.end()) { tails.push_back(x); } else { *it x; } } return tails.size(); }注意非递减版本的tails数组性质也会相应变化它不再是严格递增而是非递减二分依然成立。用这个模板去解LeetCode上的“最长递增子序列变体”时一定要先看清题目要求的是严格递增还是非递减这是经验里的高频分水岭。4.2 还原真实子序列p数组配合逆向扫描很多题目只要求长度但有些工程场景或者面试追问会让你“输出这个子序列本身”。前面说过直接用tails输出是错的。正确做法是在O(nlogn)过程中额外维护一个pos数组记录每个原数组元素在tails中的“插入位置”然后逆序还原子序列。具体思路当处理nums[i]时记录它落在tails的哪个下标从0开始记为pos[i]。这个pos[i]的含义是“以nums[i]结尾的最长递增子序列的长度减1”。为什么因为nums[i]要么是追加此时pos[i]等于之前的tails长度要么是替换此时pos[i]是某个已存在位置但无论哪种情况它都代表“当前以nums[i]结尾可以形成的最长递增子序列长度”。有了pos数组我们从后往前扫描找出pos值等于最终LIS长度-1的元素作为子序列最后一个元素然后找pos值等于上一个位置-1且在原数组中该元素之前的元素。由于逆序扫描时我们不受顺序限制可以保证原数组的先后关系。vectorint getLIS(vectorint nums) { int n nums.size(); vectorint tails, pos(n); for (int i 0; i n; i) { auto it lower_bound(tails.begin(), tails.end(), nums[i]); pos[i] it - tails.begin(); if (it tails.end()) { tails.push_back(nums[i]); } else { *it nums[i]; } } int len tails.size(); vectorint res(len); // 逆序扫描从后往前找pos值依次递减的元素 for (int i n - 1; i 0 len 0; i--) { if (pos[i] len - 1) { res[len - 1] nums[i]; len--; } } return res; }注意一个细节逆序扫描时我们用“pos值从大到小递减”来选元素从最后一个元素开始往前匹配。因为pos值是从1开始的对应长度1所以len从tails.size()开始倒推。从后往前保证原数组的相对顺序因为后面匹配的元素在原数组中的下标一定大于前面匹配的元素的下标这样得到的天然是合法子序列顺序。4.3 二维LIS变体嵌套信封问题的拆解思路除了非递减变体另一个高频考点是二维的LIS最典型的例子是“俄罗斯套娃信封问题”。给定一堆信封的宽和高一个信封A能装进信封B当且仅当A的宽和高都小于B的宽和高。问最多能嵌套多少个信封。这道题的处理技巧非常经典分成两步第一步按宽度从小到大排序在宽度相同的情况下按高度从大到小排序。后者的原因是为了避免在宽度相等时被错误地嵌套进去。因为高度降序排宽度相等的信封在高度上不会形成递增关系这样我们在对高度求LIS时宽度相同的信封之间无法互相转移。第二步在排序后的高度数组上求LIS严格递增得到的长度就是最多信封嵌套数。这个思路的关键是“先排序降维把二元比较变成一元LIS”。很多二维、甚至三维的LIS问题都可以用类似方法降维处理比如“在时间轴上的事件顺序问题”或者“按某个属性排序后再求另一属性的LIS”。4.4 其他需要留意的变体动态LIS与带权LIS还有一种题目会要求“支持动态修改数组询问当前LIS长度”这已经属于进阶的数据结构范畴了一般需要线段树或者平衡树维护。核心思想是把值域看成一维坐标线段树上维护“以小于某个值结尾的最长递增子序列长度”每次单点修改后询问前缀最大值。这类题虽然比赛里不常见但部分公司的笔试里会出。另外还有“带权最长递增子序列”也就是每个元素的长度权重不是1而是给定的某个值要求最大化权重和而不是长度。这种题和LIS的最大区别是状态定义不再等价于“长度”因为在相同长度时不同选择对应的权重和不同不能简单用“最小末尾”来贪心。一般会退回到O(n²)的DP并在转移时使用最大值加权重的写法。遇到这类题目别硬套O(nlogn)的尾巴要结合具体状态好好分析。5. 常见问题与排查技巧实录5.1 二分边界错误导致结果偏大或偏小手写二分的时候最容易出的问题就是边界判断。一个常见的错误是在找到目标位置后没有区分“追加”和“替换”两种情况导致tails数组长度偏大或偏小。我调试最多的一种场景是把if (it tails.end())写成了if (it tails.begin())然后在非空数组上操作时逻辑完全乱掉。这类问题的排查思路很简单在小数组上逐步打印tails的变化比如[1,3,2]每一步记录tails的值看它是否符合预期。用纸笔手动模拟两三组数据比对着屏幕猜要高效得多。还有一种情况是二分里用了导致死循环。比如有些写错的方法使用left right但mid更新时写成了left mid在没有1的情况下在mid位置最终会出现死循环。我建议手写二分时固定使用“左闭右开”模板避免这类低级错误。5.2 状态初始化错误导致空数组或单元素数组报错O(n²) DP中如果对空数组不提前返回直接在dp.size()上操作会报错或者返回错误结果。我的习惯是任何涉及到子序列的题目先判断n是否等于0等于0就直接返回0。这是一个极其简单但容易被忽略的边界条件。单元素数组的情况也需要注意ans初始化为1和初始化为0会导致两种不同结果。如果不处理n1的情况把ans初始化为1循环能正常执行返回1如果把ans初始化为0需要在循环内部或结束后额外判断。为了避免这种不必要的复杂度我直接选择在开头做边界判断并把ans初始化为1。5.3 把tails直接当LIS输出导致结果与预期不符这是我在项目里实际遇到的一个问题。当时需要输出最长递增子序列本身用于日志分析我直接调用O(nlogn)的函数返回长度然后用“辅助数组逆推”的方式输出。结果发现直接输出tails得到的结果和原数组某些顺序对不上。经过排查才意识到tails数组只是各长度最小末尾的“代表”并不保证这些代表在原数组中的相对顺序恰好构成一个递增子序列。所以如果面试官或者题目要求输出具体的序列一定不要图省事直接返回tails。要么用上面提到的pos数组逆序扫描方法要么老老实实写O(n²)的DP并在转移时记录前驱节点pre数组。前者时间效率高后者实现更直观根据场景取舍即可。我这里把常见问题整理成一个速查表方便你复习的时候快速对照问题错误表现正确做法空数组崩溃或返回0提前判断n0直接返回0ans初始化错误单元素数组返回0ans初始为1先判断n0严格递增写成非递减结果偏大比较用二分用lower_bound非递减写成严格递增结果偏小比较用二分用upper_bound直接把tails当结果输出序列与预期不符用pos数组逆序还原二分模板错误结果不确定/死循环固定用左闭右开left0rightlenmid在循环内更新5.4 一个容易忽略的小技巧用纸笔模拟与打印调试我在调试LIS相关题目时最大的习惯是所有涉及二分的算法先用纸笔走一遍小数组。比如[3,1,2,4,2]这种看似简单的序列手动走一遍tails的每一步变化能极大帮助确认自己对lower_bound和upper_bound的理解。很多问题不是代码写错而是对算法流程本身的理解有偏差手推一遍就全清楚了。另外在写二分查找时我建议在关键位置加上断言或者打印输出观察每次查找返回的位置是否符合直觉。比如处理元素2时tails是[1,3,4]lower_bound(2)应该返回下标1如果返回了下标2说明你写成了upper_bound或者边界有误。这类肉眼可见的错误调试几下就能定位。6. 最后再分享两个实战心得首先O(nlogn)解法与O(n²)解法在面试中的定位是完全不同的。O(n²)更多是展示你对动态规划基本概念的理解O(nlogn)则是展示你对贪心和二分的掌握程度。不少面试官会在你给出O(n²)解法后追问能不能优化到O(nlogn)这时候如果能顺利讲出来说明你不仅会套模板还理解贪心背后的数学原理。我在实际项目里用到LIS的场景也很有趣一次是做监控趋势分析需要从一堆时间序列数据中找出“最长的持续上升区间”。这个场景最初想用滑动窗口解决后来发现数据有噪声、需要容忍局部波动最后发现本质上是在做“最长递增子序列”的变体。项目数据量不大O(n²)的DP就够用但如果数据量达到百万级别就只能上O(nlogn)的解法了。最后再分享一个小技巧刷LIS类题目时建议把这四道题放在一起做效果非常明显第一道是最基础的LIS长度第二道是输出LIS序列本身第三道是把严格递增改成非递减第四道是二维信封问题。做完这四道题LIS相关的变体和陷阱基本就都见过了面试场上再遇到也不会慌。动态规划这个东西说到底就是“定义状态、找到转移、处理边界”三件事。LIS作为动态规划的经典入门题用来体会这三件事再合适不过了。把这题吃透后面的编辑距离、背包问题、最长公共子序列都会有更好的手感。 
长河君 · 2026/10/15 17:01:39 · 阅读 1.2k 动态规划之最长递增子序列：从O(n²)到O(nlogn)的优化
刷题刷到动态规划这一块的时候最长递增子序列Longest Increasing SubsequenceLIS几乎是绕不开的一道题。我印象太深了某次面试里被问到“怎么在O(nlogn)时间内求LIS长度”我第一反应就是“n平方的dp不香吗”结果对面一句话把我问住了“如果n是10万呢”当场卡壳回去把这题翻来覆去研究了整整两天才发现这里面的门道比想象中深得多。这篇内容就是围绕“算法Day09-动态规划之最长递增子序列”这个主题展开的。我会把从暴力递归到O(n²)动态规划再到O(nlogn)贪心二分的完整演进路径讲清楚包括状态定义为什么这么写、二分法到底在二分什么、以及最容易被忽视的“如何还原真实递增子序列”这个问题。无论你是刚开始接触动态规划的入门选手还是刷题到中期想搞懂优化原理的进阶玩家这篇内容应该都能给你一些启发。1. 先把问题本身看得透透的1.1 问题定义里的两个陷阱在动手写代码之前我建议先把问题定义一个字一个字地抠清楚。什么是最长递增子序列给定一个数组比如[10,9,2,5,3,7,101,18]要求找到一个最长的子序列满足两个条件第一子序列不要求连续。这一点和子数组subarray有本质区别。子数组必须是原数组中连续的一段而子序列只是保持元素在原数组中的相对顺序中间可以跳元素。比如上面数组里[2,3,7,101]就是一个合法的子序列它们在原数组中的下标是2、4、5、6中间跳过了5和3完全没问题。正因为不连续这个特性才会引出后面那一堆动态规划的状态设计如果要求连续那直接用滑动窗口就能解决就谈不上什么“最长递增子序列”了。第二递增是严格递增还是非递减。这是面试里极其常见的变体稍不留神就会写错。严格递增意味着后一个元素必须大于前一个元素也就是nums[j] nums[i]相等的情况不能算数。但有些题会改成非递减那就变成了nums[j] nums[i]代码里的比较符号要改二分的策略也要相应调整。这个问题我后面专门开一节详细讲因为真的太多人在这里栽跟头。1.2 为什么暴力解法走不通理解了问题定义之后初学者最自然的想法是把所有递增子序列都枚举出来然后挑最长的。这在理论上是可行的但在实际中完全跑不动。一个长度为n的数组子序列的个数是2^n个就算剪枝掉大量非递增的情况最坏情况下枚举所有组合依然是指数级复杂度。当n20时2的20次方是1048576勉强能跑但n30时已经超过10亿了n50基本上就是天文数字。所以我们需要一个更聪明的办法。你会发现判断一个子序列是否递增其实只需要关注当前子序列的最后一个元素。也就是说状态转移只和“以某个元素结尾的递增子序列长度”有关之前具体选了哪些元素并不重要。这个“只需要记住当前最优状态、不需要记住过程细节”的思想正是动态规划能够把指数级问题降到多项式级复杂度的核心原因。用大白话说就是走一步看一步每次只需要根据前一步的最优结果来更新当前步子不需要回头把所有走过的路都重新走一遍来比较。1.3 动态规划的思考路径三个关键问题很多教程上来就直接甩状态定义和转移方程读者看得一头雾水。我觉得更重要的事情是建立一套思考路径面对任何动态规划题目先问自己三个问题第一个问题状态是什么在这个题目里“以某个位置为结尾的递增子序列的最大长度”是唯一需要维护的信息。这里的关键词是“以某个位置结尾”这是很多子序列类DP题目的惯用套路。第二个问题转移关系是什么如果我知道了所有在位置i之前且值小于nums[i]的元素j所对应的最优长度那么以i结尾的最长递增子序列长度就是这些dp[j]的最大值加1。这里体现的是最优子结构性质全局最优解可以由局部最优解组合而成。第三个问题边界条件是什么数组里任何一个单独的元素自身就是一个长度为1的递增子序列所以所有dp[i]初始化为1。想明白这三个问题O(n²)的解法就呼之欲出了。而O(nlogn)的解法则是在“转移关系”这一步做了优化用二分查找代替了线性扫描。下面我一步步来拆。2. O(n²)动态规划最直观的基线解2.1 状态定义与转移方程的由来我们定义dp[i]表示“以nums[i]这个元素结尾的最长递增子序列的长度”。这里特别要注意“以nums[i]结尾”意味着nums[i]必须被选入子序列并且是整个子序列的最后一个元素。这个限制非常关键它保证了我们在讨论dp[i]时有一个明确的归属点可以供后续转移使用。转移方程是dp[i] max(dp[i], dp[j] 1) 其中 0 j i 且 nums[j] nums[i]为什么这样转移因为如果nums[j] nums[i]那就意味着我可以把nums[i]接到以nums[j]结尾的那个递增子序列后面形成一个新的、长度加1的递增子序列。那么对于所有满足条件的j我找到一个能让我接上去之后长度最大的那个得到的就是dp[i]的最优值。举个例子数组[1,3,2,4]。dp[0]1因为只有1自己。i1时nums[1]3下标0的nums[0]1小于3所以dp[1]dp[0]12。i2时nums[2]2下标0的1小于2所以dp[2]dp[0]12下标1的3不小于2跳过。注意这里dp[2]并不能从dp[1]转移过来因为3不能接到2后面。i3时nums[3]4下标0的1、下标1的3、下标2的2都小于4分别对应dp[0]12、dp[1]13、dp[2]13取最大值得到dp[3]3。答案就是dp数组的最大值3对应子序列[1,2,4]或[1,3,4]。2.2 代码实现与边界处理代码写起来非常直接如果按照我前面说的状态定义来写就是两个for循环嵌套。注意外层是当前位置i内层扫描所有ji的位置。int lengthOfLIS(vectorint nums) { int n nums.size(); if (n 0) return 0; vectorint dp(n, 1); int ans 1; for (int i 0; i n; i) { for (int j 0; j i; j) { if (nums[j] nums[i]) { dp[i] max(dp[i], dp[j] 1); } } ans max(ans, dp[i]); } return ans; }有一个非常容易踩的细节ans应该初始化为1还是0如果数组为空直接返回0这是针对题目约束的空数组边界。如果数组非空那么至少有一个元素答案至少是1所以ans初始化为1没问题。但如果你的ans初始化为0并且数组只有一个元素那么内层循环不会执行ans会一直保持0最后返回0这就错了。虽然有些写法会在循环里处理但我个人习惯是先处理n0的case然后把ans初始化为1从i0开始正常循环。分情况讨论比依赖初始值更保险。2.3 复杂度分析与优化信号这个解法的时间复杂度是O(n²)空间复杂度是O(n)。外层循环n次内层循环最多n次总操作次数约等于n(n-1)/2也就是n²量级。当n10万时n²等于100亿这个量级在现代计算机上大概要跑几十秒到几分钟完全不符合大部分算法题的时限。所以问题就来了能不能把内层的线性扫描改成更快的方式我们可以拆解一下内层循环到底在做什么在已经扫描过的所有元素中找到所有值小于当前元素的那些位置取出其中dp值最大的一个。这里有两个维度一个是值的大小nums[j] nums[i]另一个是dp值的大小。有没有一种数据结构可以同时处理这两个维度这就是O(nlogn)解法的出发点。仔细想一想dp值有一个非常重要的单调性质如果nums[j] nums[k]且j k那么dp[j]最多等于dp[k]实际上通常dp[k] dp[j]因为以nums[k]结尾的序列长度至少不会比以nums[j]结尾的短只要nums[k]大于nums[j]的话可以直接接上。这个性质可以沿用到“用dp值分组”的思路。不过更优雅的解法其实是反过来思考不看dp值而是去看“长度为len的递增子序列它的最小末尾元素是多少”。这就是下一节的耐心排序思想。3. 进阶解法贪心二分O(nlogn)拿下3.1 从“维护最小末尾”开始理解先说结论。我们可以维护一个数组tails其中tails[i]表示“长度为i1的所有递增子序列中末尾元素的最小值”。这句话是理解整个O(nlogn)解法的钥匙我建议你多读几遍直到完全消化。这个tails数组有两个重要的性质性质一tails是严格递增的。证明很简单如果长度为i2的递增子序列末尾元素是x那么它去掉最后一个元素后剩下的是一个长度为i1的递增子序列其末尾元素必然小于x。所以长度为i2的递增子序列的最小末尾一定大于长度为i1的递增子序列的最小末尾。所以tails[i] tails[i1]恒成立。性质二tails的长度就是LIS的长度。因为tails数组中有多少个元素就说明存在长度为1、2、3……直到len的递增子序列所以最长递增子序列长度就是tails数组的size。有了性质一我们就可以对tails做二分查找了。这也是整个优化方案能够成立的关键tails有序所以查找可以用二分复杂度从线性降到对数级别。处理每个元素nums[i]的策略如下在tails中二分查找第一个大于等于nums[i]的位置pos。如果pos等于tails的长度说明nums[i]比tails里所有元素都大把它追加到尾部这代表我们找到了一个更长的递增子序列。否则用nums[i]替换掉tails[pos]。这个替换的意义是长度相同的递增子序列我们保留更小的末尾元素因为更小的末尾元素更有利于后续元素的拼接相当于“给未来留下更大的空间”。这就是经典的贪心策略的朴素解释很多人管它叫“耐心排序”Patience Sorting因为它在纸牌游戏里就是用来计算最少牌堆数的。3.2 为什么替换是正确的而不丢解初学者最容易质疑的一点是“用nums[i]替换tails[pos]会不会丢弃掉某些可能的更长序列”我们把问题想透。tails[pos]记录的是长度为pos1的递增子序列的最小末尾值。现在我们发现了一个新的长度为pos1的递增子序列其末尾值nums[i]更小也就是说这个新序列比原来记录的那个序列“更值得被延伸”。因为任何原本可以接在tails[pos]后面的元素一定可以接在nums[i]后面nums[i]比tails[pos]更小条件更宽松所以替换之后只会让未来更好不会让未来更差。而且注意替换操作并不会改变tails数组的最大长度也就是说它不会让你丢失已经求得的当前LIS长度。它做的是“同长度内部的优化”把每个长度的代表性值尽可能压小从而为后续更大的元素留出更长的接力跑道。这个思想你可以类比成你在找一个递增的长途队列队列越往后需要的人越“高”。如果前一个位置来了个更矮的人赶走原来的高个子让矮个子站这个位置后面再来的高个子反而更容易排进队伍里。整个过程不会让队伍变短只会让它有更多变长的机会。3.3 二分查找的正确写法代码如下我用的是C标准库的lower_bound它返回的是第一个大于等于目标值的迭代器。int lengthOfLIS(vectorint nums) { vectorint tails; for (int x : nums) { auto it lower_bound(tails.begin(), tails.end(), x); if (it tails.end()) { tails.push_back(x); } else { *it x; } } return tails.size(); }如果你不熟悉lower_bound可以看一下手写二分的版本int lengthOfLIS(vectorint nums) { vectorint tails; for (int x : nums) { int left 0, right tails.size(); while (left right) { int mid left (right - left) / 2; if (tails[mid] x) { left mid 1; } else { right mid; } } if (left tails.size()) { tails.push_back(x); } else { tails[left] x; } } return tails.size(); }注意我这里手写二分时left初始化为0right初始化为tails.size()这是一个“左闭右开”的区间。循环条件是left right最终left就是我们要找的位置。有不少人会在这里把边界写错最常见的是把right初始化成tails.size()-1然后用left right结果在空数组时直接越界。我的建议是统一用“左闭右开”这套模板不容易出错也方便记忆。3.4 复杂度对比与面试时的表述策略两种方法的时间、空间复杂度放在一起看非常清晰解法时间复杂度空间复杂度适用场景O(n²) DPO(n²)O(n)n 5000要求能还原子序列时O(nlogn) 贪心二分O(nlogn)O(n)n 10^4 的大规模数据在面试中我一般会先快速给出O(n²)的DP解法表示理解了问题的本质然后追问“如果数据量变大怎么办”再过渡到O(nlogn)解法。这两种解法一条主线讲下来面试官对你的印象分通常不会低。但这里必须指出一个非常关键的坑O(nlogn)的解法只回答了“长度是多少”如果要还原真实的递增子序列直接输出tails数组是错的这一点我见太多人踩了。举个例子数组[3,1,2,4]我们用tails过程推一下处理3tails变成[3]处理1替换3tails变成[1]处理2追加tails变成[1,2]处理4追加tails变成[1,2,4]。这里tails刚好等于真实LIS因为1本来是排在3后面的幸运地保持了下来。但如果数组是[1,3,2,4]处理1tails[1]处理3tails[1,3]处理2替换3tails[1,2]处理4tails[1,2,4]。这里tails是[1,2,4]和真实LIS一致因为2在3后面虽然替换了但数组顺序没毛病。再看[3,2,1,4]处理3tails[3]处理2替换3tails[2]处理1替换2tails[1]处理4tails[1,4]。真实LIS其实是[3,4]或者[2,4]或者[1,4]tails输出[1,4]虽然长度正确但也就罢了。最经典的坑是[10,9,2,5,3,7,101,18]tails最终是[2,3,7,18]但真实LIS可以是[2,5,7,101]或者[2,3,7,101]18根本不在正确答案里。因为18替换了101而101是在18后面出现的合法序列末尾替换操作导致了“覆盖”而不是“追加”tails数组里的值并不保证是真实子序列。那要还原真实子序列怎么办需要借助DP的思想辅助记录。在后面我会专门讲这个技巧。4. 从模板到实战变体情况与代码改造4.1 严格递增改非递减一个符号和一个二分边界的差别有相当多的题目会在LIS的基础上要求“非递减”而不是“严格递增”比如“最长不下降子序列”。改动点有两个第一个是O(n²) DP里的比较符号从nums[j] nums[i]改成nums[j] nums[i]。这很好理解允许相等元素的接续。第二个是O(nlogn)解法里的二分策略严格递增时我们要找的是第一个大于等于当前元素的位置用lower_bound非递减时如果当前元素等于tails里的某个值我们不能把它接到相等的元素后面因为如果允许相等那就可以直接接上所以我们需要找到第一个大于当前元素的位置也就是把“等于”也视为可追加的情况。在C里这个操作是upper_bound返回第一个大于目标值的迭代器。int lengthOfLISNonDecreasing(vectorint nums) { vectorint tails; for (int x : nums) { auto it upper_bound(tails.begin(), tails.end(), x); if (it tails.end()) { tails.push_back(x); } else { *it x; } } return tails.size(); }注意非递减版本的tails数组性质也会相应变化它不再是严格递增而是非递减二分依然成立。用这个模板去解LeetCode上的“最长递增子序列变体”时一定要先看清题目要求的是严格递增还是非递减这是经验里的高频分水岭。4.2 还原真实子序列p数组配合逆向扫描很多题目只要求长度但有些工程场景或者面试追问会让你“输出这个子序列本身”。前面说过直接用tails输出是错的。正确做法是在O(nlogn)过程中额外维护一个pos数组记录每个原数组元素在tails中的“插入位置”然后逆序还原子序列。具体思路当处理nums[i]时记录它落在tails的哪个下标从0开始记为pos[i]。这个pos[i]的含义是“以nums[i]结尾的最长递增子序列的长度减1”。为什么因为nums[i]要么是追加此时pos[i]等于之前的tails长度要么是替换此时pos[i]是某个已存在位置但无论哪种情况它都代表“当前以nums[i]结尾可以形成的最长递增子序列长度”。有了pos数组我们从后往前扫描找出pos值等于最终LIS长度-1的元素作为子序列最后一个元素然后找pos值等于上一个位置-1且在原数组中该元素之前的元素。由于逆序扫描时我们不受顺序限制可以保证原数组的先后关系。vectorint getLIS(vectorint nums) { int n nums.size(); vectorint tails, pos(n); for (int i 0; i n; i) { auto it lower_bound(tails.begin(), tails.end(), nums[i]); pos[i] it - tails.begin(); if (it tails.end()) { tails.push_back(nums[i]); } else { *it nums[i]; } } int len tails.size(); vectorint res(len); // 逆序扫描从后往前找pos值依次递减的元素 for (int i n - 1; i 0 len 0; i--) { if (pos[i] len - 1) { res[len - 1] nums[i]; len--; } } return res; }注意一个细节逆序扫描时我们用“pos值从大到小递减”来选元素从最后一个元素开始往前匹配。因为pos值是从1开始的对应长度1所以len从tails.size()开始倒推。从后往前保证原数组的相对顺序因为后面匹配的元素在原数组中的下标一定大于前面匹配的元素的下标这样得到的天然是合法子序列顺序。4.3 二维LIS变体嵌套信封问题的拆解思路除了非递减变体另一个高频考点是二维的LIS最典型的例子是“俄罗斯套娃信封问题”。给定一堆信封的宽和高一个信封A能装进信封B当且仅当A的宽和高都小于B的宽和高。问最多能嵌套多少个信封。这道题的处理技巧非常经典分成两步第一步按宽度从小到大排序在宽度相同的情况下按高度从大到小排序。后者的原因是为了避免在宽度相等时被错误地嵌套进去。因为高度降序排宽度相等的信封在高度上不会形成递增关系这样我们在对高度求LIS时宽度相同的信封之间无法互相转移。第二步在排序后的高度数组上求LIS严格递增得到的长度就是最多信封嵌套数。这个思路的关键是“先排序降维把二元比较变成一元LIS”。很多二维、甚至三维的LIS问题都可以用类似方法降维处理比如“在时间轴上的事件顺序问题”或者“按某个属性排序后再求另一属性的LIS”。4.4 其他需要留意的变体动态LIS与带权LIS还有一种题目会要求“支持动态修改数组询问当前LIS长度”这已经属于进阶的数据结构范畴了一般需要线段树或者平衡树维护。核心思想是把值域看成一维坐标线段树上维护“以小于某个值结尾的最长递增子序列长度”每次单点修改后询问前缀最大值。这类题虽然比赛里不常见但部分公司的笔试里会出。另外还有“带权最长递增子序列”也就是每个元素的长度权重不是1而是给定的某个值要求最大化权重和而不是长度。这种题和LIS的最大区别是状态定义不再等价于“长度”因为在相同长度时不同选择对应的权重和不同不能简单用“最小末尾”来贪心。一般会退回到O(n²)的DP并在转移时使用最大值加权重的写法。遇到这类题目别硬套O(nlogn)的尾巴要结合具体状态好好分析。5. 常见问题与排查技巧实录5.1 二分边界错误导致结果偏大或偏小手写二分的时候最容易出的问题就是边界判断。一个常见的错误是在找到目标位置后没有区分“追加”和“替换”两种情况导致tails数组长度偏大或偏小。我调试最多的一种场景是把if (it tails.end())写成了if (it tails.begin())然后在非空数组上操作时逻辑完全乱掉。这类问题的排查思路很简单在小数组上逐步打印tails的变化比如[1,3,2]每一步记录tails的值看它是否符合预期。用纸笔手动模拟两三组数据比对着屏幕猜要高效得多。还有一种情况是二分里用了导致死循环。比如有些写错的方法使用left right但mid更新时写成了left mid在没有1的情况下在mid位置最终会出现死循环。我建议手写二分时固定使用“左闭右开”模板避免这类低级错误。5.2 状态初始化错误导致空数组或单元素数组报错O(n²) DP中如果对空数组不提前返回直接在dp.size()上操作会报错或者返回错误结果。我的习惯是任何涉及到子序列的题目先判断n是否等于0等于0就直接返回0。这是一个极其简单但容易被忽略的边界条件。单元素数组的情况也需要注意ans初始化为1和初始化为0会导致两种不同结果。如果不处理n1的情况把ans初始化为1循环能正常执行返回1如果把ans初始化为0需要在循环内部或结束后额外判断。为了避免这种不必要的复杂度我直接选择在开头做边界判断并把ans初始化为1。5.3 把tails直接当LIS输出导致结果与预期不符这是我在项目里实际遇到的一个问题。当时需要输出最长递增子序列本身用于日志分析我直接调用O(nlogn)的函数返回长度然后用“辅助数组逆推”的方式输出。结果发现直接输出tails得到的结果和原数组某些顺序对不上。经过排查才意识到tails数组只是各长度最小末尾的“代表”并不保证这些代表在原数组中的相对顺序恰好构成一个递增子序列。所以如果面试官或者题目要求输出具体的序列一定不要图省事直接返回tails。要么用上面提到的pos数组逆序扫描方法要么老老实实写O(n²)的DP并在转移时记录前驱节点pre数组。前者时间效率高后者实现更直观根据场景取舍即可。我这里把常见问题整理成一个速查表方便你复习的时候快速对照问题错误表现正确做法空数组崩溃或返回0提前判断n0直接返回0ans初始化错误单元素数组返回0ans初始为1先判断n0严格递增写成非递减结果偏大比较用二分用lower_bound非递减写成严格递增结果偏小比较用二分用upper_bound直接把tails当结果输出序列与预期不符用pos数组逆序还原二分模板错误结果不确定/死循环固定用左闭右开left0rightlenmid在循环内更新5.4 一个容易忽略的小技巧用纸笔模拟与打印调试我在调试LIS相关题目时最大的习惯是所有涉及二分的算法先用纸笔走一遍小数组。比如[3,1,2,4,2]这种看似简单的序列手动走一遍tails的每一步变化能极大帮助确认自己对lower_bound和upper_bound的理解。很多问题不是代码写错而是对算法流程本身的理解有偏差手推一遍就全清楚了。另外在写二分查找时我建议在关键位置加上断言或者打印输出观察每次查找返回的位置是否符合直觉。比如处理元素2时tails是[1,3,4]lower_bound(2)应该返回下标1如果返回了下标2说明你写成了upper_bound或者边界有误。这类肉眼可见的错误调试几下就能定位。6. 最后再分享两个实战心得首先O(nlogn)解法与O(n²)解法在面试中的定位是完全不同的。O(n²)更多是展示你对动态规划基本概念的理解O(nlogn)则是展示你对贪心和二分的掌握程度。不少面试官会在你给出O(n²)解法后追问能不能优化到O(nlogn)这时候如果能顺利讲出来说明你不仅会套模板还理解贪心背后的数学原理。我在实际项目里用到LIS的场景也很有趣一次是做监控趋势分析需要从一堆时间序列数据中找出“最长的持续上升区间”。这个场景最初想用滑动窗口解决后来发现数据有噪声、需要容忍局部波动最后发现本质上是在做“最长递增子序列”的变体。项目数据量不大O(n²)的DP就够用但如果数据量达到百万级别就只能上O(nlogn)的解法了。最后再分享一个小技巧刷LIS类题目时建议把这四道题放在一起做效果非常明显第一道是最基础的LIS长度第二道是输出LIS序列本身第三道是把严格递增改成非递减第四道是二维信封问题。做完这四道题LIS相关的变体和陷阱基本就都见过了面试场上再遇到也不会慌。动态规划这个东西说到底就是“定义状态、找到转移、处理边界”三件事。LIS作为动态规划的经典入门题用来体会这三件事再合适不过了。把这题吃透后面的编辑距离、背包问题、最长公共子序列都会有更好的手感。