从LeetCode 300到Vue 3 diff：最长递增子序列算法全解析

刷算法题经常遇到一种情况：题目看着不复杂，暴力解法随手就能写，但一提交就超时，然后看完题解又觉得“不过如此”。LeetCode 的 300. 最长递增子序列（Longest Increasing Subsequence）就是这类题里非常有代表性的一个。它表面上是道经典动态规划题，但内里藏着一个近乎贪心的二分优化，而且这个优化思路还被 Vue 3 的 diff 算法拿去解决节点移动问题了。如果你最近在刷 Hot 100，或者研究 Vue 3 源码里的 diff 逻辑，这道题无论如何都绕不过去。

这篇文章不打算给你抄一段题解就完事，而是把这道题从暴力到动态规划再到 O(n log n) 优化的完整推导过程过一遍，同时把 Vue 3 里“求最长递增子序列”这件事和这个算法真正联系起来讲清楚。无论你是刚开始刷题的算法新手，还是想搞明白前端框架底层原理的前端开发，这篇都能给你一些不太会写在题解里的东西。

1. 题目拆解与核心思路

1.1 题目到底在问什么

先看一下题面：

给你一个整数数组 nums，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

这里有两个关键信息。

第一，“子序列”不是“子数组”。子数组要求元素在原数组中连续，子序列不要求连续，只要保持相对顺序就行。比如 [1,2,3,4,5] 里，[1,3,5] 是子序列但不是子数组。很多人一开始做这道题时会下意识往连续子数组方向想，这是第一个坑。

第二，“严格递增”意味着后一个元素必须大于前一个元素，相等不算递增。比如 [2,2] 这个序列，严格递增子序列的长度只能是 1，不能是 2。

搞清楚这两个前提，题目实际上就问的是：在一个无序序列中，挑出一些元素，保持原来的相对顺序，让它们形成一个严格递增的序列，这个序列最长能有多长。

1.2 暴力解法为什么不能直接用

最直观的暴力做法是枚举所有子序列。一个长度为 n 的数组，每个元素有选和不选两种状态，子序列总数是 2^n 个，对于每个子序列还要花 O(n) 时间判断是否递增，总复杂度是 O(n · 2^n)。

n 稍微大一点，比如 2500，这直接就是天文数字。所以暴力思路只能作为理解题目的起点，不能作为答案。

从暴力思路往优化的方向走，其实问题的关键变成了这样一个疑问：我能不能不枚举所有子序列，而是想办法记录并复用已经计算过的结果？这正是动态规划的切入点。

1.3 两条主流解法路线

题目本身有两类解法，对应两种不同的复杂度：

动态规划的思路更直观，适合作为理解这类题的基础。贪心 + 二分是这道题的精髓所在，也是面试中最容易被追问的部分，更是 Vue 3 diff 算法中实际使用的方案。两条线都有必要吃透。

2. 动态规划：以 O(n²) 先建立直觉

2.1 状态定义为什么是 dp[i]

动态规划最核心的就是状态定义。这道题里，最自然的定义是：

dp[i] 表示以 nums[i] 这个元素作为结尾的最长递增子序列的长度。

为什么一定要“以 nums[i] 结尾”？因为递增子序列的扩展需要知道目前末尾元素的值，只有知道末尾元素，才能判断下一个新元素能不能接上去。如果定义的 dp[i] 是“前 i 个元素中”的最长递增子序列长度，那转移时会丢失子序列末尾信息，没法正确扩展。

这个定义很像往事：你想知道以当前人物为结局的故事最长能有多长，就必须知道走到当前人物之前的状态。dp[i]就是在记录“以当前元素结尾时，故事最长能多长”。

2.2 状态转移方程推导

假设我们已经知道了所有 dp[0]，dp[1]，…，dp[i - 1] 的值，现在要算 dp[i]。

我们把 nums[i] 接到哪个位置的后面，才能保证仍然递增？答案是：任何一个 j < i 且 nums[j] < nums[i] 的位置。在所有这些可接的位置里，选一个 dp[j] 最大的，再加 1，就是 dp[i]。用公式写出来就是：

dp[i] = max(dp[j] + 1)，其中 0 ≤ j < i 且 nums[j] < nums[i]

如果前面没有任何一个元素小于 nums[i]，那 dp[i] = 1，也就是 nums[i] 自己单独构成一个长度为 1 的递增子序列。

最终答案不是 dp[n - 1]，而是 max(dp[0], dp[1], …, dp[n - 1])，因为最长递增子序列不一定以最后一个元素结尾。

2.3 完整代码与推演示例

def lengthOfLIS(nums): 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)

拿一个实际例子推演一下，假设 nums = [10, 9, 2, 5, 3, 7, 101, 18]：

• dp[0] 对应 nums[0] = 10，没有前面的元素，dp[0] = 1
• dp[1] 对应 nums[1] = 9，前面只有 10，但 10 > 9，接不上，dp[1] = 1
• dp[2] 对应 nums[2] = 2，前面的 10 和 9 都大于 2，dp[2] = 1
• dp[3] 对应 nums[3] = 5，前面只有 2 < 5，dp[3] = dp[2] + 1 = 2，表示子序列 [2, 5] 长度为 2
• dp[4] 对应 nums[4] = 3，前面 2 < 3，dp[4] = dp[2] + 1 = 2，表示子序列 [2, 3]
• dp[5] 对应 nums[5] = 7，前面 2、5、3 都小于 7，其中 dp[3] = 2、dp[4] = 2，所以 dp[5] = 3，表示 [2, 5, 7] 或 [2, 3, 7]，长度 3
• dp[6] 对应 nums[6] = 101，前面所有小于 101 的元素里，dp[5] = 3 最大，所以 dp[6] = 4，即 [2, 3, 7, 101] 或 [2, 5, 7, 101]
• dp[7] 对应 nums[7] = 18，前面小于 18 的元素里 dp[5] = 3 最大，dp[7] = 4，即 [2, 3, 7, 18] 或 [2, 5, 7, 18]

整个数组的最长递增子序列长度是 4，结果正确。

2.4 时间复杂度的瓶颈

O(n²) 的解法可以轻松处理 n = 2500，但 LeetCode 上这道题的常见数据范围是 n ≤ 2500 甚至更大，O(n²) 在某些变体题里是不够用的。问题出在内层循环：每计算一个 dp[i] 都得从头扫描前面所有元素。

有没有办法把内层循环从“扫描所有 j”变成“快速定位到某个位置”？这就要引出贪心 + 二分的思路了。

3. 贪心 + 二分：进入 O(n log n) 的世界

3.1 核心思想：把“尽可能大的长度”和“尽可能小的末尾值”绑定

O(n²) 的做法时间主要花在反复扫描前缀上。换个角度想，如果我们需要找一个地方把 nums[i] 接上去，最理想的情况是：对于一个固定的子序列长度，末尾值越小越好，因为越小越容易在后面接上更多元素。

这个直觉是整道题优化思路的钥匙。基于这个想法，我们可以维护一个数组 d，其中：

d[len] 表示所有长度为 len 的递增子序列中，末尾元素的最小值。

注意这里 d 的下标是“长度”，不是“位置”。这个数组一定是一个严格递增的数组。为什么？因为如果长度为 i 的递增子序列的末尾最小值是 x，长度为 i + 1 的递增子序列一定是从长度为 i 的递增子序列后面接一个更大的元素得到的，所以长度为 i + 1 的末尾最小值必然大于长度为 i 的末尾最小值。d 数组的严格递增性保证了二分查找的可行性，这是整个优化的理论基础。

3.2 遍历过程中发生了什么

我们遍历数组里的每个数 x，然后做这件事：在 d 数组里找到第一个大于等于 x 的位置，把那个位置的值替换成 x。

为什么替换？原因可以这样理解：

• 如果 x 比 d 数组当前所有值都大，那说明 x 可以接到当前最长递增子序列的末尾，子序列长度加 1，把 x 追加到 d 数组最后。
• 如果 x 不是最大的，那它不能扩展最长子序列，但它比某个长度的子序列原本的末尾值更小，把它放进去，未来在这个长度上有更多扩展空间。

用字面来比喻：d 数组就像是维护着“每个长度下的最小潜力值”。看到一个新数时，要么把它加进潜力池子成为新长度的起点，要么用它更新某个长度的潜力下限。

来看一个推演，还是 nums = [10, 9, 2, 5, 3, 7, 101, 18]：

• 初始 d = []
• x = 10，d 为空，直接放入，d = [10]。此时最长长度为 1
• x = 9，找到第一个 ≥ 9 的位置是 0，替换，d = [9]。最长长度仍为 1
• x = 2，第一个 ≥ 2 的位置是 0，替换，d = [2]。最长长度 1
• x = 5，所有元素（只有 2）都小于 5，追加，d = [2, 5]。最长长度 2
• x = 3，第一个 ≥ 3 的位置是 1，替换，d = [2, 3]。最长长度 2
• x = 7，所有元素（2, 3）都小于 7，追加，d = [2, 3, 7]。最长长度 3
• x = 101，所有元素都小于 101，追加，d = [2, 3, 7, 101]。最长长度 4
• x = 18，第一个 ≥ 18 的位置是 3，替换，d = [2, 3, 7, 18]。最长长度仍为 4

最终 d 数组长度为 4，表示最长递增子序列长度为 4。注意 d 数组是 [2, 3, 7, 18]，但真实的最长递增子序列是 [2, 3, 7, 101] 或 [2, 5, 7, 18] 或 [2, 3, 7, 18]。d 数组不一定是实际子序列，它只负责记录长度不变时的“更小末尾值”，从而留出更多扩展空间。

3.3 二分的边界条件：为什么找的是“第一个大于等于 x 的位置”

这里有一个非常容易搞错的细节：我们要找的是第一个大于等于 x 的位置，不是第一个大于 x 的位置，也不是最后一个小于 x 的位置。

具体来说：

• 如果 x 没有改变任何位置，说明 x 比 d 数组里所有元素都大，那么应该追加到末尾，扩展最长长度。
• 如果用“第一个大于 x”的位置来替换，会出现什么问题？当 x 等于 d 中某个值时，严格递增子序列里相同的值不能出现在同一个序列里，所以相等的情况下应该替换掉那个相等的位置，把“潜力”更新到相同长度的序列上。找“第一个大于等于”刚好把相等的值也覆盖掉。

面试里如果让你写二分，这两个边界是高频考点。用 Python 标准库的话，bisect_left就是找第一个大于等于的位置，bisect_right找的是第一个大于的位置，这里必须用bisect_left。

3.4 正确性直觉：为什么替换不影响最终长度

很多人第一次看到这个操作会觉得离谱：“把等于 5 的位置替换成 3，之前那个长度为 2 的子序列不是被破坏了吗？后续统计长度不就错了吗？”

关键理解是：d[i] 不是一个真实的子序列，它只是“长度为 i + 1 的递增子序列的最小末尾值”。把 5 替换成 3，等于告诉系统：“现在长度为 2 的递增子序列，我可以做到以 3 结尾，这比以 5 结尾更利于后面的扩展。”之前那个 [2, 5] 序列其实并没有消失，它只是被一个潜力更大的 [2, 3] 取代了。所有 d 里更长的序列，都是从更短的序列扩展来的，如果短序列的末尾变得更小，长序列只会更容易形成，不会更难。

这个思想跟现实中的“长远规划”很像：同样花两年攒了 10 万块，你是希望维持现状，还是换个收入含金量更高的工作，以同样的经验积累获取更大的复利空间？尾值越小，未来能接的元素越多，这是本质逻辑。

3.5 代码实现

import bisect def lengthOfLIS(nums): d = [] for x in nums: pos = bisect.bisect_left(d, x) if pos == len(d): d.append(x) else: d[pos] = x return len(d)

这个实现总共只遍历一次数组，每次在 d 数组上做 O(log n) 的二分查找，所以总时间是 O(n log n)。空间上用了一个 d 数组，O(n)。

4. 不是冷知识：Vue 3 diff 里的最长递增子序列

4.1 Vue 3 diff 到底在干什么

如果你接触过 Vue 2 的 virtual DOM diff，大概知道 Vue 2 的 diff 算法在对比新旧子节点列表时，通过双端指针进行预处理，对无法命中预处理的场景做全量更新。Vue 3 在这方面做了大幅优化，其中一个核心点就是引入了一个函数：getSequence。

Vue 3 中 diff 的过程大致是这样的：

1. 对比新旧子节点，标记出哪些节点是新增的、哪些是删除的、哪些是需要移动位置的。
2. 为了尽量少移动 DOM，就要找出不需要移动的节点，或者说出所有需要移动的节点中的“稳定序列”。
3. 这个“稳定序列”就是新旧子节点对比后，索引变化关系里的最长递增子序列。

具体来说，当新旧两个子节点列表中有一批节点共有时，Vue 会为这些共有节点生成一个在新列表中的位置索引数组，然后在这个数组上求最长递增子序列。最长递增子序列里的节点是相对顺序没有变化的节点，它们不需要移动。其余不在这个子序列里的节点才需要移动。这样就能把 DOM 移动次数降到最少。

4.2 为什么是 O(n log n) 而不是 O(n²)

Vue 源码运行时的性能很关键，如果这个函数是 O(n²)，对于大量子节点的更新就会卡。所以它采用了和 LeetCode 300 完全一样的贪心 + 二分思路，只不过实现时还要额外维护一个p数组（前驱数组）来记录每个位置的前驱结点，以便最后回溯出真正的子序列，而不仅仅是长度。

这也就是为什么 Vue 源码里的getSequence看起来和 LeetCode 的解法“有点像但又不完全一样”：它需要在实际运行时输出一个下标序列，用来告诉 diff 算法“这几个节点顺序稳定，不要动它们”。

4.3 getSequence 的一个简化版解读

Vue 源码里的getSequence(arr)核心逻辑可以简化成下面这段缩写版代码（不是 Vue 源码本身，而是等价思路）：

function getSequence(arr: number[]): number[] { const result: number[] = [] const p = arr.slice() // 前驱记录 for (let i = 0; i < arr.length; i++) { const item = arr[i] if (item === 0) continue let left = 0 let right = result.length - 1 while (left <= right) { const mid = Math.floor((left + right) / 2) if (arr[result[mid]] < item) { left = mid + 1 } else { right = mid - 1 } } if (left === result.length) { result.push(i) } else { result[left] = i } if (left > 0) { p[i] = result[left - 1] } } // 回溯 let u = result.length let v = result[u - 1] while (u-- > 0) { result[u] = v v = p[v] } return result }

这里的result数组只存索引，p数组记录每个索引位置在最长序列中的前驱索引，最后通过回溯还原出真实的最长递增子序列的索引列表。Vue 拿到这些索引后，就知道哪些虚拟节点可以跳过移动操作，直接复用 DOM。

4.4 算法和工程的边界：长度够用 vs 序列可回溯

LeetCode 300 只求长度，所以贪心 + 二分的实现完全不需要回溯。Vue 的 diff 需要知道具体是哪些节点不需要动，所以引入了额外的前驱回溯。

这是一种很典型的“从算法题到工程应用”的跃迁：算法题往往只问你长度，工程里你往往需要的是方案本身。如果你只看过 LeetCode 题解，可能没法意识到这个问题；如果你直接看 Vue 源码又会觉得里面那段 getSequence 有点难懂。把两端连起来看，整个逻辑就通了。

5. 一些人容易踩的坑和实际调试建议

5.1 初始化 dp 数组时全填 1 对不对

对，不对的是最后返回dp[n - 1]。很多人第一次写 DP 版时，会把 dp 全部初始化为 1，然后最终 return 最后一个位置的 dp 值。这在某些数据上会出错，比如[3, 2, 1]，最长递增子序列长度是 1，dp 数组全 1，返回 dp[2] = 1 没问题；但[1, 3, 6, 7, 9, 4, 10, 8]这种情况，最长递减区间在中间，最长递增子序列可能不以最后一个元素结尾，必须返回所有 dp 的最大值。

5.2 贪心 + 二分版得到的 d 数组不是真实子序列

这是最容易被面试官追问的点。d = [2, 3, 7, 18]不代表真实子序列是[2, 3, 7, 18]，它只是表示“长度为 4 的递增子序列存在，且最小末尾值可以做到 18”。如果你面试时被问到“能给出具体子序列吗”，你需要额外维护前驱数组来追溯。Vue 的 getSequence 就是活生生的例子。

5.3 二分查找到底用bisect_left还是bisect_right

LeetCode 300 这道题要求严格递增，相同值不能出现在子序列中，所以用bisect_left。如果你遇到变体题要求非严格递增（后一个元素可以等于前一个元素），那就要把条件改成bisect_right，也就是找第一个大于 x 的位置。这两个 api 在标准库里都有，区别只在于遇到相同值时的处理方式。

5.4 如何快速手写二分

面试时不能用标准库怎么办？写一个在 d 数组中查找第一个大于等于 x 的位置的二分模板：

def lower_bound(d, x): left, right = 0, len(d) while left < right: mid = (left + right) // 2 if d[mid] < x: left = mid + 1 else: right = mid return left

这个模板的循环不变量是：左闭右开区间 [left, right) 内始终包含答案。结束时 left == right，这个位置就是第一个满足 d[mid] >= x 的下标。

5.5 一维 DP 还能不能再优化

有些变体题会给障碍条件，或者要求输出具体序列，这时候朴素的 O(n²) 就不够用了。进阶方向是“对 dp 值做分桶 + 线段树维护区间最大值”，能用 O(n log n) 求出区间最大值版的最长递增子序列。不过对于 300 这道题来说，贪心 + 二分已经是最优做法了。

6. 从这道题还能延伸出去的思路

6.1 变体一：最长递减子序列

把递增条件反过来就是最长递减子序列。处理方式很简单：对整个数组取负数，再求最长递增子序列。因为递增和递减是对称的，这个技巧在很多竞赛题里都非常常用。

6.2 变体二：二维最长递增子序列（信封嵌套）

LeetCode 上有一道俄罗斯套娃信封问题：每个信封有宽和高，如果 a 信封的宽和高都大于 b 信封，就可以把 b 套进 a，问最多能套几层。这道题的做法是先按宽度升序排序，宽度相同时按高度降序排序，然后对高度数组求最长递增子序列。宽度相等时高度降序可以避免宽度相同的信封互相嵌套，细节很值得玩味。

6.3 变体三：最长递增子序列个数

LeetCode 673 要求输出最长递增子序列的个数，此时需要维护每个位置的 dp 值和对应组合数量。这个变体对状态定义的深度理解要求更高，也是面试评级里常见的加分题。

7. 我实际刷这道题时的一些体会

这道题我前后大概刷过三遍。第一遍只会 O(n²) 的动态规划，觉得这题不过如此；第二遍接触到贪心 + 二分时，被 d 数组的做法惊到了，但当时没有完全理解为什么替换元素不会丢掉潜在的子序列；第三遍是在研究 Vue 3 源码时，发现getSequence的注释和实现逻辑，才把这道题彻底吃透。

如果让我给一个刷题顺序建议，我会说：先把 O(n²) 的 DP 完整写对，能讲清楚状态定义和转移方程；再去手写贪心 + 二分的版本，并确保自己能在白板上推导一遍完整的过程；最后再看 Vue 3 的getSequence源码，把算法和工程实践串起来。这样一轮下来，这道题就不再是一道孤立的题，而是一把能撬动多个领域的钥匙。

[] [] 试问一个算法模板能支撑多少个场景？从 LeetCode 的普通题目到 Vue 3 源码的 diff 优化，最长递增子序列这个算法在不同表层下反复出现。如果你正在准备面试，建议把这道题做到能默写、能讲解、能扩展到变体，而不是看到「AC 通过」就匆匆进入下一题。毕竟会刷题的人不少，能把算法本质讲清楚的人，才是面试官更愿意给机会的人。