Diff 算法贪心策略解析：Vue 复用逻辑深度揭秘

Vue 3 的 Diff 算法采用贪心策略，通过求解旧节点在新序中“最长递增子序列”（LIS）来最大化复用不动节点，将复杂度降至 O(n log n)；该策略依赖 stable key 建立索引映射，并以二分查找加速 LIS 构建，不回溯、不穷举，兼顾性能与实效。

Diff 算法中的“贪心”策略，不是指随意选、凑合用，而是指在每一步匹配中，**优先保留那些已经处于相对正确位置的节点，不为追求理论最优而反复试探，直接采纳当前看来最稳妥的复用选择**。Vue（尤其是 Vue 3）正是靠这个思路，在保证 DOM 更新最小化的前提下，把算法复杂度从 O(n²) 降到了 O(n log n)。

贪心策略在 Diff 中具体怎么体现？

它不试图穷举所有可能的节点移动方案，而是聚焦一个核心目标：**找出旧列表中“最长递增子序列”（LIS）——即那些在新顺序里依然保持相对位置正确、且无需移动就能复用的节点**。

• 所谓“递增”，在这里指节点在新数组中的索引是严格上升的；例如旧节点序列 [A, B, C, D] 对应新索引 [2, 0, 3, 1]，那么子序列 B→D（对应新索引 0→1）就是递增的
• “最长”意味着尽可能多地锁定不动节点，从而把需要 insert/move 的操作压缩到最少
• 贪心体现在：一旦确认某个节点可以纳入 LIS，就立即接受它，不再回溯重选；后续节点只和已确定的 LIS 做比较，快速决定是否扩展

为什么不用动态规划全量计算？

动态规划能算出真正的 LIS 长度，但时间复杂度是 O(n²)，对频繁更新的 UI 来说太重。Vue 3 换了一种更轻快的做法：

• 用一个辅助数组记录“长度为 k 的递增子序列末尾最小可能值”
• 对每个新索引，用二分查找快速定位它该插在哪——这步是 O(log n)
• 整个过程一遍扫描完成，总复杂度 O(n log n)，兼顾速度与效果
• 虽然不保证数学意义上绝对最长，但在真实 DOM 场景中，复用率和性能表现足够优秀

贪心如何直接提升节点复用率？

复用率高，本质是“不动的节点多”。贪心策略通过 LIS 把这个问题转化成：找出最多有多少个节点，它们在新旧顺序中的相对关系没变。

• 比如旧列表渲染的是 [用户头像, 昵称, 签名, 关注按钮]，新列表变成 [昵称, 关注按钮, 用户头像, 签名]
• 算法会发现“昵称→用户头像→签名”这一组（新索引 0→2→3）天然有序，优先保留它们
• 只需把“关注按钮”插入到第 1 位，其他三个节点原地复用，避免了全部打散重建
• 这种局部保序思维，比逐个对比标签名或 key 更高效，也比暴力重排更节省资源

它和“key”的关系是什么？

key 是贪心策略生效的前提，但不是全部：

• 没有 key，Vue 只能按位置硬匹配，哪怕内容完全一样，位置一变就被当成新节点
• 有稳定 key，Vue 才能准确识别“哪个旧节点对应哪个新节点”，进而算出它们在新顺序里的索引映射
• 贪心策略是在 key 对齐后的索引序列上运行的——它不管节点长什么样，只看“这些带 key 的节点，在新数组里该怎么排才最省事”