什么是 Diff 算法的“贪心”策略？深度解析 Vue 提高复用率的逻辑-Vue.js-PHP中文网

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

什么是 diff 算法的“贪心”策略？深度解析 vue 提高复用率的逻辑

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 做比较，快速决定是否扩展