1. 从一道经典面试题说起为什么“最长递增子序列”值得反复刷如果你在刷 LeetCode Hot 100大概率绕不过300. 最长递增子序列这道题。它的题目描述特别简单给你一个整数数组 nums找到其中最长严格递增子序列的长度。子序列不要求连续但它必须保持原数组中的相对顺序。比如[10,9,2,5,3,7,101,18]最长递增子序列是[2,3,7,101]长度为 4。我第一次刷这道题的时候内心是有点不以为然的觉得不就是“找递增序列嘛”结果一上手发现暴力枚举子序列是 2 的 n 次方根本跑不动用动态规划能优化到 O(n^2)但数据量一大还是心里没底。直到后来学到“贪心 二分”的 O(n log n) 解法才明白这道题真正的精髓不在“求长度”而在于它背后埋伏着的一整套“如何优化状态搜索”的思路。这道题适合谁刷不只是准备面试的后端工程师前端工程师更应该认真吃透它。为什么因为 Vue3 的 Diff 算法里为了尽量少移动真实 DOM 节点核心就用到了“最长递增子序列”的思想。你可以在很多面经里看到这个组合拳LeetCode 300 Vue3 diff 优化。如果你能从一个算法题延伸到框架源码的实现面试官对你的评价会明显不一样。所以这篇文章我会把这道题从 O(n^2) 到 O(n log n) 的完整解法讲透再手把手拆解它在 Vue3 Diff 中的实际应用。2. 第一层解法动态规划把问题拆成“以 i 结尾的最长序列”2.1 状态定义与转移方程动态规划的第一步永远是想清楚状态。对于这道题我习惯的定义是dp[i]表示以nums[i]这个元素作为结尾的最长递增子序列的长度。这个定义很自然因为一个递增子序列一定要有一个“结尾元素”而且它必须是原数组里的某个元素。那dp[i]怎么由前面的状态推导出来呢我们可以扫描i之前的所有位置j只要满足nums[j] nums[i]那么nums[i]就可以接在以nums[j]结尾的那个递增子序列后面长度就是dp[j] 1。取所有可能情况的最大值就是dp[i]。写成转移方程就是dp[i] max(dp[j] 1) 其中 0 j i 且 nums[j] nums[i]如果前面没有比nums[i]小的元素那nums[i]只能自己单独成为一个子序列所以dp[i]至少是 1。因此初始化时所有dp[i]都设为 1。这里有个初学者特别容易踩的坑dp[i]不是整个数组的最优解而是“以 i 结尾”的局部最优解。最终答案不是dp[n-1]而是所有dp[i]里的最大值。比如数组[1,3,6,7,9,4,10,5,6]的最长递增子序列是[1,3,6,7,9,10]长度为 6但以最后一个元素6结尾的最长递增子序列只有[1,3,4,5,6]长度是 5不是全局答案。这个细节在笔试里经常被忽略。2.2 代码实现与复杂度分析用 JavaScript 实现 O(n^2) 的动态规划非常直接function lengthOfLIS(nums) { const n nums.length; if (n 0) return 0; const dp new Array(n).fill(1); let result 1; for (let i 1; i n; i) { for (let j 0; j i; j) { if (nums[j] nums[i]) { dp[i] Math.max(dp[i], dp[j] 1); } } result Math.max(result, dp[i]); } return result; }时间复杂度是 O(n^2)因为外层循环 i 枚举每个位置内层循环 j 要扫描之前所有位置。空间复杂度是 O(n)用来存 dp 数组。这个方案在 n 5000 时还能跑但一旦 n 到 10 万O(n^2) 就是 10 亿次操作直接超时。所以必须寻找更优策略。动态规划的价值并不仅仅是这段代码更重要的是它给了我们一个“状态如何积累”的范本。很多变种题比如“最长递增子序列的个数”“俄罗斯套娃信封问题”第一步都还是先定义 dp[i]然后再根据条件做转移。所以哪怕后面有了更快的解法动态规划的思维也一定要先掌握扎实它是你理解一切优化的起点。2.3 动态规划 vs 子数组两个最容易混淆的概念提到最长递增子序列很多人会和“最长连续递增子序列”混淆。LeetCode 674 那道题要求的是连续子数组比如[1,3,5,4,7]的最长连续递增子数组是[1,3,5]长度 3而最长递增子序列可以是[1,3,4,7]长度 4。差别就在“连续”二字上。连续递增子数组的 dp 转移只需要看前一个元素if (nums[i] nums[i-1]) dp[i] dp[i-1] 1 else dp[i] 1复杂度 O(n)。而子序列问题因为可以跳过中间元素必须回头扫描所有前面的元素所以复杂度就是 O(n^2)。这个区别在面试里经常被追问你回答案的时候如果能主动点出“子序列问题通常比子数组问题多一个维度的枚举”面试官会觉得你确实理解透了。3. 第二层解法贪心 二分把复杂度降到 O(n log n)3.1 核心思想维护一个“最小的末尾元素”数组O(n^2) 的解法慢在哪儿慢在每到一个新元素都要和之前所有元素比较一遍。这个过程能不能加速能但需要一个巧妙的观察。我们定义一个数组tails其中tails[i]表示长度为i 1的递增子序列中可能的最小末尾元素值。注意关键词是“最小”。为什么最小因为末尾元素越小这个子序列就越容易在后面接上新的、更大的元素所以“最小末尾”等价于“最有潜力”的子序列。举个例子假设当前已经处理到[1,3,5]tails数组是[1,3,5]。此时来了一个新元素4它比3大但比5小它能接在[1,3]后面形成[1,3,4]这个序列长度为 3末尾是 4比原来的[1,3,5]末尾更小。于是我们把tails[2]长度为 3 的最小末尾从5更新成4。这个更新不会影响已经算出的长度但会让后续元素更容易形成更长的递增子序列。这就是贪心思想不断用更小的末尾去“优化”未来。那么如何利用tails计算长度呢当我们遍历到nums[i]时在tails中寻找第一个大于等于nums[i]的位置pos。如果pos等于tails的当前长度说明nums[i]比所有已知的末尾都大可以直接接在最后面形成一个新的、更长的递增子序列所以tails.push(nums[i])。否则用nums[i]更新tails[pos]。最终tails.length就是最长递增子序列的长度。因为tails数组是严格递增的这里需要严格递增因为原题要求严格递增子序列所以可以用二分查找定位pos把每次查找的时间从 O(n) 降到 O(log n)。3.2 一步一步模拟看懂二分替换的过程用nums [10, 9, 2, 5, 3, 7, 101, 18]来走一遍完整流程初始tails []。读10tails为空直接放入。tails [10]读9二分找到第一个大于等于9的位置是下标 0用9替换10。tails [9]。这一步很重要9比10小但同样能构成长度为 1 的子序列且潜力更大。读2替换下标 0。tails [2]读55比2大插入到最后。tails [2, 5]读3第一个大于等于3的是下标 1 的5替换为3。tails [2, 3]读7比3大插入。tails [2, 3, 7]读101比7大插入。tails [2, 3, 7, 101]读18第一个大于等于18的是下标 3 的101替换为18。tails [2, 3, 7, 18]最终tails.length 4正确答案就是 4。注意tails数组是[2,3,7,18]但它并不是真实的最长递增子序列只是“能拼出最长长度的最小末尾集合”。如果面试官追问“如何输出最长递增子序列本身”那光靠tails是不够的需要额外记录一个position数组再逆序回溯。这个方法我在文末会补充。3.3 代码实现注意二分查找的边界条件function lengthOfLIS(nums) { const tails []; for (const num of nums) { let left 0, right tails.length; // 在 tails 中找第一个 num 的位置 while (left right) { const mid (left right) 1; if (tails[mid] num) { left mid 1; } else { right mid; } } if (left tails.length) { tails.push(num); } else { tails[left] num; } } return tails.length; }这里有一个经典边界问题如果原题要求“非严格递增”也就是允许相等元素那二分查找条件要改成“第一个大于 num 的位置”也就是在tails[mid] num时移动左边界。一句话总结严格递增用非严格递增用。我当年就是因为没区分这个在一道“最长非递减子序列”的题上卡了半天后来才明白这是两个相邻但不同的模板。时间复杂度外层循环 O(n)内层二分 O(log n)总 O(n log n)。空间 O(n)。这个复杂度在 LeetCode 上已经是最优解n 到 10^6 也能轻松扛住。4. 跳出算法Vue3 Diff 中的“最长递增子序列”优化4.1 Vue2 的 diff 痛点频繁移动 DOM 节点聊完算法本身咱们看看它在真实世界中最让我兴奋的应用Vue3 的 Diff 算法。Vue2 的虚拟 DOM Diff 使用的是双端比较策略也就是定义四个指针oldStartIndex、oldEndIndex、newStartIndex、newEndIndex然后循环执行四种比较头头、尾尾、头尾、尾头。这种策略在同级节点顺序基本不变、只是首尾插入或删除时效率很高。但一旦遇到“中间大量节点位置互换”的场景Vue2 就会进入一种低效的更新模式它会对旧子节点列表建一个 key 到索引的映射表然后通过遍历新列表逐个判断节点是否需要移动。移动的规则是维护一个“当前最大索引”如果新节点在原列表中的索引小于这个最大索引就说明需要移动。这个“小于最大索引就要移动”的规则非常粗糙。比如原列表[A, B, C, D, E]新列表[A, C, D, B, E]按照 Vue2 的逻辑当遍历到B时它在旧列表中的索引是 1而当前最大索引已经到 4因为C索引 2、D索引 3、E索引 4 都更新过于是B会判定为需要移动。但实际情况是B只需要移动到E前面即可Vue2 的做法可能让多个节点都被反复移动产生更多次真实 DOM 操作。真实 DOM 操作是性能杀手所以这个优化空间非常大。4.2 Vue3 的优化思路预处理 最长递增子序列Vue3 的 diff 做了几个关键动作第一步同步处理头部和尾部的相同节点。新旧两个子节点列表如果从头开始比较节点相同就直接复用并 patch指针往后走从尾部开始比较相同也直接复用。这样可以把“完全没变的最外层骨架”先剔除掉剩下来的就是真正需要处理的中间部分。第二步对剩余的新节点建立 key 到索引的映射然后遍历旧节点列表生成一个“新索引数组”。如果旧节点在新列表里不存在说明被删除了如果存在就把新索引记录下来如果不存在就标记为新增。这个过程中的删除与新增操作是必须做的但“移动”操作则是可以优化的。第三步针对剩下的可复用节点基于它们在新列表中的索引序列计算这个序列的“最长递增子序列”。比如剩余旧节点的索引数组是[5, 2, 3, 4]最长递增子序列是[2, 3, 4]对应旧节点里的三个节点它们的相对位置在新列表里已经是对的了所以它们不需要移动。只需要把不在这个子序列里的节点比如索引5对应的节点移过去就行。这样一来实际发生的 DOM 移动次数降至最低这就是 Vue3 diff 性能提升的核心秘密。我画过一张很简陋的手绘图来理解这个过程这里用文字描述一下假设旧子节点为[C, D, E, B]新子节点为[D, E, B, C]。头部比较C和D不同尾部比较B和C不同所以全部进入中间处理。旧列表中的D在新列表索引为 0E为 1B为 2C为 3于是索引数组是[0, 1, 2, 3]这是个完全递增的序列最长递增子序列就是全部因此所有节点都不需要移动只需要调整位置顺序即可其实这里还需要根据真实 DOM 插入锚点来操作实际上由于整个序列递增Vue3 会认为旧节点顺序和新节点顺序一致根本不会产生移动。但新列表的顺序明明是[D, E, B, C]旧列表是[C, D, E, B]位置已经变了为什么不需要移动呢因为 Vue3 只关心“最终如何通过插入和删除达到新状态”当可复用节点的相对顺序没有发生改变时它们作为一个整体不用移动只需要把多出来的节点比如这里的C插入到正确位置即可。这个概念需要仔细琢磨我建议你自己在纸上画一画新旧列表和索引关系很快就能通。4.3 静态提升与 patchflag为什么 diff 变快了不止一个量级很多人把 Vue3 diff 变快的原因单纯归功于最长递增子序列其实不完整。Vue3 在编译阶段还做了两个很重要的优化静态提升和 patch flag。静态提升是指对于模板中不依赖响应式数据的节点Vue3 在编译时会将它们提升到render函数外部创建一次虚拟节点对象之后每次重新渲染直接复用同一个对象不再重复创建。这就大大减少了虚拟节点的创建开销。Vue2 每次 diff 都会重新创建一遍所有 vnode即使内容没变也得走一遍创建和比较。patch flag 是指Vue3 在编译时会给每个动态节点打上标记告诉 diff 过程“这个节点只有 class 变了”“那个节点只有文本变了”等等。diff 时只需要精确比较带 flag 的部分而不是对整个 vnode 做全量属性比对。比如一个节点绑定了动态:class编译后会标记patchFlag 2diff 时只比较 class 相关属性。最长递增子序列、静态提升、patch flag 三者在 diff 性能优化中扮演的角色不同静态提升减少“创建”的成本patch flag 减少“比较”的成本最长递增子序列减少“移动”的成本。这三板斧合在一起才是 Vue3 虚拟 DOM 性能全面超越 Vue2 的真正原因。面试时如果能这样分层回答一定会让面试官觉得你有真实的源码阅读功底而不是只背了一堆八股。5. 手写实现一个可用的 LIS 函数并用它理解 Vue3 的 diff 思路5.1 返回索引序列的 LIS 实现Vue3 源码里的getSequence函数返回的是最长递增子序列对应的索引数组而不是长度。因为 diff 过程中需要知道“哪些旧节点索引是不需要移动的”。我基于贪心 二分手写了一个可用的版本function getSequence(nums: number[]): number[] { const n nums.length; const result []; // 存储当前 LIS 的索引 const position new Array(n); // 记录每个索引在 result 中的前驱位置 for (let i 0; i n; i) { const num nums[i]; if (result.length 0 || num nums[result[result.length - 1]]) { // 如果 num 比当前 LIS 末尾元素还大直接追加 if (result.length 0) position[i] result[result.length - 1]; result.push(i); } else { // 二分查找第一个大于等于 num 的位置 let left 0, right result.length - 1; while (left right) { const mid (left right) 1; if (nums[result[mid]] num) { left mid 1; } else { right mid; } } // 替换 if (left 0) position[i] result[left - 1]; result[left] i; } } // 回溯还原真正的索引序列 let len result.length; let last result[len - 1]; while (len-- 0) { result[len] last; last position[last]; } return result; }这个函数返回的是一组索引比如[2, 3, 5]表示原数组中的第 2、3、5 个元素构成最长递增子序列。注意result在最终回溯前并不是真实索引序列只能表示长度和最小末尾必须通过position回溯才能拿到正确的索引。如果不回溯直接拿result去移动节点会得到错误结果这也是很多人抄 Vue 源码时最容易犯的错。5.2 在 Diff 中如何使用这套逻辑假设旧子节点列表oldChildren是[a, b, c, d, e]新子节点列表newChildren是[a, c, d, b, e]所有节点都有稳定的 key。头部比较a相同更新后oldStartIndex和newStartIndex都 1。尾部比较e相同更新后oldEndIndex和newEndIndex都 -1。此时剩下[b, c, d]和[c, d, b]。建立新索引映射c - 0d - 1b - 2。遍历旧列表的剩余部分[b, c, d]得到索引数组[2, 0, 1]。调用getSequence([2, 0, 1])返回的递增子序列索引是[1, 2]原数组中的下标 1 和 2对应旧节点c和d。于是c和d不需要移动只需要把b移动到正确的位置放进d和e之间。整个 diff 只需要一次真实 DOM 移动。如果使用 Vue2 的“当前最大索引”策略遍历到b时就会发现它需要移动然后遍历到c时也可能判断需要移动最终可能要移动两次。虽然例子简单但足以看出差距LIS 能保证移动次数最少。5.3 一个容易误解的点LIS 计算的不是“节点值”而是“新索引”我见过不少人把 Vue3 里的 LIS 理解成“对节点本身的 key 值求最长递增子序列”这是不对的。Vue3 求的 LIS 是针对“旧节点在新列表中的索引位置”组成的数组。为什么因为我们要找的是“在旧列表中保持相对顺序不变的那些节点”而判断相对顺序是否不变就是要看它们在新列表中的索引是否递增。如果旧节点 A 和 B 在新列表中的索引分别是 1 和 3A 在旧列表中排在 B 前面新列表中 A 仍然排在 B 前面因为 1 3说明它们的相对顺序没变就不需要移动 A 或 B。只有那些破坏了递增关系的节点才需要移动。举个例子如果 A 在新列表索引是 3B 在新列表索引是 1旧列表 A 在 B 前面但新列表 B 到了 A 前面相对顺序变了这两个节点中至少有一个需要移动。LIS 优化的目标就是找出“最多的一组不需要移动的节点”从而把需要移动的节点数量降到最低。这个转换思路也是算法题“变体”的高频考法将序列问题转化为索引问题再用 LIS 求解。比如 LeetCode 1713 题“得到子序列的最少操作次数”就是先把 target 中字符在 arr 中的位置映射出来然后求位置数组的 LIS目标长度与 LIS 的差值就是最少操作次数。掌握这种“映射到索引再求解”的套路可以解决一大类问题。6. 常见问题与排查技巧实录6.1 关于 LIS 题型的五问五答速查表以下是实际刷题和面试复盘时最常遇到的几个问题我整理成了速查表问题原因/答案为什么 dp 数组初始化为 1每个元素自身一定能构成一个长度为 1 的递增子序列即使后面没有比它大的元素结果至少是 1。为什么tails数组最终长度是答案但内容不是答案tails只记录“当前长度下最小可能的末尾值”用于贪心扩展真实子序列需要额外记录前驱回溯。二分查找时用还是严格递增子序列用找第一个大于等于 num 的位置非严格递增允许相等用找第一个大于 num 的位置。Vue2 和 Vue3 diff 中移动节点判断有什么本质区别Vue2 用“新节点在旧索引中是否小于当前最大索引”判断可能过度移动Vue3 先求最长递增子序列只移动不在子序列里的节点移动次数最少。LIS 能处理负数和重复值吗能。负数不影响算法重复值只在严格递增时需要注意二分条件如果允许相等按非严格递增改条件即可。6.2 刷题时的三个血泪教训第一个教训别拿tails数组长度做输出序列的关联。我一开始以为tails就是最长递增子序列结果在 LeetCode 上用自定义用例测试时发现长度正确但元素不对。比如[1,3,6,7,9,4,10,5,6]tails最终是[1,3,4,5,6]长度是 5而真实最长子序列是[1,3,6,7,9,10]长度是 6这里长度都不对因为例子没跑完。总之tails的长度能稳定表示 LIS 长度但内容不是 LIS 本身。明白这个边界才能避免在“输出路径”类问题里踩坑。第二个教训二分查找的右边界一定要写对。在tails里查找时右边界应该是tails.length因为要找的是“第一个大于等于 num 的插入点”如果所有元素都小于 num插入点就是数组末尾。很多实现把右边界写成tails.length - 1遇到「num 比所有元素都大」的情况就会让左边索引超出数组范围必须单独判断。用while (left right) 最终left tails.length的分支可以省去一堆边界特判。第三个教训在 Vue3 源码中getSequence返回的是索引数组不是节点数组。我第一次尝试阅读 Vue3runtime-core的renderer.ts时看到getSequence返回一个数组下意识以为是 key 数组结果在调试时完全对不上号。后来才明白它返回的是“不需要移动的节点的索引”这些索引指向的是剩余旧节点列表中的位置而不是全局索引也不是 key 值。调试这类代码时建议在源码里临时加 console.log 打印每一步的newIndexToOldIndexMap和getSequence的结果配合一个小用例很快就能理清整个流程。6.3 如何把 LIS 拓展到更多场景掌握了底层的 LIS 算法后你会遇到很多“包装过的 LIS 问题”。最常见的变种是二维 LIS比如 LeetCode 354“俄罗斯套娃信封问题”。信封有宽和高一个信封能套进另一个当且仅当宽和高都严格大于。解法是先按宽度升序排序如果宽度相同按高度降序排序然后对高度数组求 LIS。为什么宽度相同要按高度降序因为相同宽度的信封不可能互相套入按降序排列可以避免它们在 LIS 中被选在一起从而巧妙地把二维问题降维成一维 LIS。还有一类变种是“最长递增子序列的个数”LeetCode 673。这类题需要在动态规划的基础上额外维护一个count数组转移时如果dp[j] 1 dp[i]就更新数量如果相等就累加数量。这个变种非常考察对状态转移的精细理解不会做的话建议先回去把基础版 dp 写一百遍再说。另一个实用场景是“下一次更新时如何利用 LIS 的某些性质做优化”比如典型的patience sorting纸牌排序算法它和 LIS 的贪心 二分解法本质上是同一个东西。当你把牌堆初始化为空每次拿出新牌放到“最左边牌顶大于等于这张牌”的堆上时堆的数量就是 LIS 长度。这个游戏化的理解方式能帮你把抽象算法具象化面试时如果被问到“为什么贪心二分是对的”可以从纸牌堆的角度打个比方每个牌堆顶部的牌就是这个长度的最小末尾选择最左边的可放堆保证后续牌有更多选择空间。7. 我在实际调试中的一些个人体会最后分享一点我在工作里遇到的真实状况特别是作为前端工程师为什么要理解这个东西。我在一个后台管理项目中做过一个长列表拖拽排序的需求列表项特别多每次拖拽后都要重新渲染整个列表。最初用的 Vue2当列表顺序混乱得比较厉害时界面会有轻微卡顿。后来我换到 Vue3 并利用key稳定的特性发现大部分拖拽后的更新都只移动了少数几个节点体感明显流畅了很多。这背后就是 LIS 算法在起作用拖拽造成的局部变动会让 Vue3 计算出最少需要移动的 DOM 节点而不是像 Vue2 那样“见到乱序就大片移动”。我后来还做过一个组件需要把频繁变化的子组件列表顺序和另一个系统保持一致。当时没有直接使用虚拟滚动而是自己写了一个简化版的“diff 节点移动”逻辑核心就是记录旧列表节点在新列表中的索引位置求 LIS标记不需要移动的节点再对需要移动的节点做批量插入。这个思路帮我减少了对 DOM 的操作次数在 localStorage 同步场景下性能提升很可观。虽然业务里直接用 Vue3 的 diff 就行但自己动手实现一遍才能真正理解框架的设计哲学。如果你也在刷 LeetCode 300我的建议是先老老实实把 O(n^2) 的 dp 写熟再逼自己不看答案写出 O(n log n) 的贪心 二分最后去阅读 Vue3 源码里的getSequence函数。这三步走完这道题对你来说就不再是“背一道题”而是一把能打开“算法优化 框架设计”双重大门的钥匙。