1. 背景与目的#
在 Vue 3 的 Diff 算法（patchKeyedChildren）中，当新旧节点列表出现乱序（Unknown Sequence）时，为了将 DOM 移动操作降到最低，Vue 需要找出一组“不需要移动的节点”。
这组节点必须满足两个条件：
- 相对顺序不变（即在旧列表和新列表中顺序一致）。
- 长度尽可能长（留下的越多，移动的越少）。
这就是 最长递增子序列 (Longest Increasing Subsequence, LIS) 的应用场景。Vue 3 采用了 贪心 + 二分查找 + 回溯 的算法，将时间复杂度压缩到了 O(n\logn)。
2. 核心变量三剑客#
理解这个算法，首先要看懂这三个变量的“分工”。
| 变量名 | 类型 | 物理含义 | 形象比喻 | 关键作用 |
|---|---|---|---|---|
arr | Array | 输入数组 | 考卷 | 新节点在旧列表中的索引序列。 |
result | Array | 结果索引集 | 草稿纸 / 指针 | 1. 存储 LIS 的索引。 2. 它的长度代表当前找到的最长序列长度。 3. 它的最后一个元素是回溯的唯一入口（HEAD指针）。 |
p | Array | 前驱节点表 | 家谱 / 树结构 | p[i] = j 表示：在 LIS 序列中，节点 i 的前一个节点是 j。它是回溯的唯一依据。 |
⚠️ 高能预警：
result和p里面存的都是arr的索引 (Index)，而不是具体的值 (Value)！
3. 核心原理升华：p 数组的本质——隐式的“多叉树”#
在阅读源码时，我们很容易把 p 仅仅看作是一个辅助数组。但如果从数据结构的视角审视，p 数组本质上就是一棵（或多棵）倒置的树（Inverted Tree）。
3.1 数组即树 (Array as Tree)#
通常树的表示是 Parent -> Children，但在这里，Vue 采用的是 Child -> Parent (p[i] = j) 的反向链接方式。
- 索引
i是树中的一个节点。 - 索引
j是i的父节点。 p数组 就是一张完整的“全量父子关系表”。
3.2 动态生长与分叉 (Branching)#
随着贪心算法的执行，这棵树会不断地分叉。每一次“替换”操作，实际上并不是删除了旧的路径，而是在某个节点上长出了一条更有潜力的新树枝。
可视化演示：
假设输入序列为 [2, 5, 8, 3, 4, 9]。算法结束时，p 数组里实际存储了这样一棵形状复杂的树：
索引0 (值2) <-- 根节点 (Root)
/ \
索引1 (值5) 索引3 (值3) <-- 发生分叉 (替换导致)
| |
索引2 (值8) 索引4 (值4)
|
索引5 (值9) <-- 最长枝的末端 (Leaf)3.3 result 的角色#
result 数组就像 Git 的 HEAD 指针。
它永远指向当前被认为是最优分支（Master）的末端。当算法把 result 的末尾从 8 换成 9 时，就像是把 HEAD 指针从一个旧分支切换到了一个更有潜力的新分支上。
4. 算法流程可视化推演#
我们使用经典案例来演示完整过程：
- 输入
arr:[2, 5, 8, 3, 4, 9] - 目标: 找出最长递增子序列的索引。
第一阶段：贪心 + 二分 (构建隐式树)#
| 步骤 | i | val | 操作逻辑 | result (存索引) | p (树结构记录) | 可视化树状态 |
|---|---|---|---|---|---|---|
| 1 | 0 | 2 | 初始：result 为空，直接放入。 | [0] | [] | 2 (根) |
| 2 | 1 | 5 | 追加：5 > 2，追加。p[1]=0。 | [0, 1] | p[1]=0 | 2 -> 5 |
| 3 | 2 | 8 | 追加：8 > 5，追加。p[2]=1。 | [0, 1, 2] | p[2]=1 | 2 -> 5 -> 8 (主干) |
| 4 | 3 | 3 | 替换：3 < 8。二分查找发现 3 比 5 小且比 2 大。替换掉 5。p[3]=0。 | [0, 3, 2](注意：这里乱序了) | p[3]=0 | 分叉！ A: 2->5->8B: 2->3 |
| 5 | 4 | 4 | 替换：4 < 8。二分查找发现 4 比 8 小且比 3 大。替换掉 8。p[4]=3。 | [0, 3, 4] | p[4]=3 | 新枝超车！ A: 2->5->8B: 2->3->4 |
| 6 | 5 | 9 | 追加：9 > 4，追加。p[5]=4。 | [0, 3, 4, 5] | p[5]=4 | 最终态 B: 2->3->4->9 |
阶段一结束状态：
result:[0, 3, 4, 5]—— 长度为 4，结尾是索引 5。p: 记录了2->5->8和2->3->4->9两条路径。
5. 深度释疑：为什么选 2,3,4,9 而不是 2,5,8,9？#
在上面的例子中，2, 5, 8, 9 和 2, 3, 4, 9 长度都是 4，都是合法的递增子序列。
为什么算法最终选择了后者？这就涉及到了“潜力（Potential）”的核心博弈。
5.1 什么是“潜力”？#
潜力指的是序列结尾数字的大小。
- 规则：结尾数字越小，后面能接纳的数字范围就越大。
- 比喻：这就像跳高比赛。你的上一跳成绩（结尾数字）就是下一跳的起跳门槛。门槛越低，后面能跳过去的人就越多。
5.2 决策时刻对比#
让我们回到算法执行到一半的关键时刻：
此时序列是 2, 5, 8。
如果不替换（保留
2, 5, 8）：当前的门槛是 8。
后果：只有大于 8 的数字（如 9, 10）才能接在后面。如果后面来的是
6或7，就接不上了，序列长度锁死在 3。如果替换（变成
2, 3, 4）：当前的门槛降到了 4。
后果：大于 4 的所有数字（5, 6, 7, 8, 9…）全都能接在后面！
5.3 算法的“上帝视角”盲区#
算法在遍历时是不知道后面还有个 9 的。它只知道：
“我现在有机会把结尾从
8降到4，虽然长度暂时没变，但我为未来创造了更多可能性。”
结果验证：
- 如果是
... 9：两个序列都能接上，打平。 - 如果是
... 6：2, 5, 8接不上（败）；2, 3, 4能接上变成2, 3, 4, 6（胜）。
结论：
算法选择 2, 3, 4 是因为它具有更高的容错率和更广的兼容性。虽然在这个特定例子中两者长度一样，但在更复杂的随机数据中，贪心策略（选小的）总是能大概率保证最终序列是最长的。
6. LIS 算法完整流程图#
下面的流程图展示了 LIS 算法从初始化到回溯的完整执行流程：
flowchart TD Start([开始]) --> Init["初始化:
p = arr.slice
result = 0
i = 0"] Init --> LoopCheck{"i 小于
arr.length?"} LoopCheck -->|是| CheckZero{"arr(i)
不等于 0?"} LoopCheck -->|否| Backtrack[回溯阶段开始] CheckZero -->|是| GetLast["获取 j =
result 末尾索引"] CheckZero -->|否| NextIter1["i 自增"] NextIter1 --> LoopCheck GetLast --> Compare{"arr(i)
大于
arr(j)?"} Compare -->|是| Append["追加操作:
p(i) = j
result.push(i)"] Compare -->|否| BinarySearch["二分查找:
找到第一个
比 arr(i) 大的位置 u"] Append --> NextIter2["i 自增"] NextIter2 --> LoopCheck BinarySearch --> CheckReplace{"arr(i) 小于
arr(result(u))?"} CheckReplace -->|是| Replace["替换操作:
if u 大于 0:
p(i) = result(u-1)
result(u) = i"] CheckReplace -->|否| NextIter3["i 自增"] Replace --> NextIter4["i 自增"] NextIter4 --> LoopCheck NextIter3 --> LoopCheck Backtrack --> BackInit["u = result.length
v = result 末尾元素"] BackInit --> BackLoop{"u 大于 0?"} BackLoop -->|是| BackRestore["result(u) = v
v = p(v)
u 自减"] BackLoop -->|否| Return([返回 result]) BackRestore --> BackLoop style Start stroke:#4caf50,stroke-width:3px style Return stroke:#4caf50,stroke-width:3px style Append stroke:#ff9800,stroke-width:2px style Replace stroke:#e91e63,stroke-width:2px style BinarySearch stroke:#2196f3,stroke-width:2px style Backtrack stroke:#9c27b0,stroke-width:2px style BackRestore stroke:#9c27b0,stroke-width:2px
7. 回溯修正 (Backtracking)#
从 result 的末尾开始，利用 p 还原真相。
- 入口：
result最后一个元素是5(对应值 9)。 - 回溯逻辑：
- 位置 End (Idx 5): 查
p[5]-> 爸爸是4(值 4)。 - 位置 Middle (Idx 4): 查
p[4]-> 爸爸是3(值 3)。覆盖 result[2]。 - 位置 Middle (Idx 3): 查
p[3]-> 爸爸是0(值 2)。覆盖 result[1]。
- 注意：这里完美的避开了索引 1 和 2 (值 5 和 8) 的那条“潜力较低”的废弃分支。
- 位置 Start (Idx 0): 查
p[0]-> 无。结束。
最终输出: [0, 3, 4, 5] (对应值 2, 3, 4, 9)。✅
8. 源码逐行精读#
function getSequence(arr) {
const p = arr.slice(); // 1. 创建 p 数组，用于记录"父节点" (隐式树结构)
const result = [0]; // 2. result 初始化，存入第0个元素的索引
let i, j, u, v, c;
const len = arr.length;
for (i = 0; i < len; i++) {
const arrI = arr[i];
// Vue 中 0 代表新增节点，不参与计算
if (arrI !== 0) {
j = result[result.length - 1]; // 获取 result 当前末尾的索引
// 【贪心策略 A】：如果当前值 > result 末尾的值
// 说明可以延长序列，直接追加
if (arr[j] < arrI) {
p[i] = j; // 关键！记录 p：当前 i 的爸爸是 j
result.push(i); // result 长度 +1
continue;
}
// 【二分查找】：如果当前值小，找到它该替换的位置
// 目标：找到第一个比 arrI 大的数
u = 0;
v = result.length - 1;
while (u < v) {
c = (u + v) >> 1; // 位运算取整
if (arr[result[c]] < arrI) {
u = c + 1;
} else {
v = c;
}
}
// 【贪心策略 B】：替换，让序列增长潜力更大
// 虽然这步操作可能导致 result 中间乱序，但为了让结尾更小（门槛更低），必须换。
if (arrI < arr[result[u]]) {
if (u > 0) {
p[i] = result[u - 1]; // 关键！记录 p：替换后，i 的爸爸变成了 u-1
}
result[u] = i; // 仅仅替换 result 中的索引
}
}
}
// 【回溯阶段】：修正 result 中的乱序，还原正确路径
u = result.length;
v = result[u - 1]; // 拿到最后一个确定的锚点 (HEAD指针)
while (u-- > 0) {
result[u] = v; // 无视 result 中间的值，直接用正确路径覆盖 (Overwrite)
v = p[v]; // 找爸爸 (沿着树往上爬)
}
return result;
}9. 总结 Q&A#
Q1: 为什么回溯时，result 中间的乱序不会导致错误？#
A: 因为回溯只信赖
result的长度和最后一个元素。 中间的元素在回溯过程中会被当做“垃圾数据”直接**覆盖（Overwrite）**掉。真正的路径关系保存在p数组 这个“只增不减”的历史档案中。
Q2: 为什么要用二分查找？#
A: 为了在
O(n\logn)的时间内完成计算。如果用遍历查找，就是 $O(n^2)$。二分查找是为了快速找到"第一个比当前元素大的数"进行替换。
Q3: 整个算法的思想精华是什么？#
“贪心 + 树结构记录”。
- 贪心：只顾当下，为了让序列结尾更小（潜力更大），甚至不惜让临时列表 (
result) 乱序。- 记录：利用
p数组构建一棵隐式的多叉树，记录每一次连接的父子关系，确保即使当前乱了，最后也能顺藤摸瓜找回来。