Vue.js 的快速 Diff 算法利用最长递增子序列（LIS）识别可复用节点以最小化 DOM 移动，先构建新节点在旧列表中的位置数组，再用贪心+二分求 LIS，据此标记不动节点并指导 patch 操作。
Vue.js 的快速 Diff 算法在处理列表更新时，并不直接暴力比对所有节点，而是借助最长递增子序列（LIS）来最小化 DOM 移动操作。它的核心目标不是找出“完全匹配”，而是确定哪些节点可以复用、哪些需要移动——而 LIS 正是求解“最少移动次数”的数学钥匙。
为什么需要 LIS？——从“移动代价”说起
当新旧 vnode 列表长度相同但顺序变化时（如 [a,b,c,d] → [b,a,d,c]），理想策略是只移动真正位置变了的节点，其余保持原位并复用。但如何判断“哪些能不动”？关键在于找出新列表中在旧列表里已有相对顺序的最长子序列。这个子序列里的节点，在 DOM 中原本就处于“正确相对位置”，无需移动；其余节点则需插入或调整。
LIS 在这里的作用是：把“节点复用+最小移动”问题，转化为一个经典的贪心动态规划问题，时间复杂度控制在 O(n log n)，远优于暴力 O(n²)。
如何构建 LIS 所需的“位置数组”？
算法第一步不是直接找子序列，而是为新列表中每个节点，查它在旧列表中的索引位置，生成一个 映射数组 newIndexToOldIndexMap：
立即学习“前端免费学习笔记（深入）”；
- 遍历新列表，对每个节点 key，查它在旧列表中最后一次出现的索引（即
oldKeyToIndex哈希表查找） - 若没找到，记为 0（表示新节点）；若找到，记下该索引值
- 最终得到一个长度为
newLength的数组，例如：[2, 0, 3, 1]（对应新节点在旧列表的位置）
这个数组中，严格递增的子序列（如 [2,3] 或 [0,1]）就代表一组在旧列表中本就“顺序靠前→靠后”的节点，它们在新列表中依然维持了这种偏序关系，因此可保留在原 DOM 位置上。
将静态 Vue 页面(index.vue)改造为动态页面(Custom.vue)；稿源仅限 index.vue、其引用的 CSS 与资源路径，禁止参考仓库内其他文件。Invoke when user wants to transform a static Vue page into a dynamic data-driven page with Element UI components.
用贪心法求 LIS，并反推“不动节点”的索引
Vue 不需要完整 LIS 序列，只需要知道哪些新节点索引属于 LIS，从而标记为“不移动”。它采用经典贪心 + 二分方式构造 LIS 的 tails 数组，并同步维护 prev 和 result 数组回溯路径：
-
tails[i]存储长度为i+1的递增子序列的最小末尾值 - 遍历位置数组时，用二分定位插入点，更新
tails，同时记录每个位置的前驱索引 - 最后从
tails最长长度处倒推，还原出 LIS 对应的新节点下标集合
这些下标对应的 vnode 就是“可原位复用、无需移动”的节点；其余节点则进入 insert/move 流程。
DOM 操作如何与 LIS 结果联动？
LIS 输出的“不动节点集合”，直接指导 patch 过程：
- 对属于 LIS 的新节点：跳过移动，仅执行 props 更新和子树 diff
- 对不属于 LIS 的节点：
- 若在旧列表中存在（key 匹配），则调用
moveNode插入到正确位置（参考其在新列表的索引） - 若不存在（key 新增），则创建新节点并插入
- 若在旧列表中存在（key 匹配），则调用
- 整个过程只需一次 DOM 插入/移动循环，避免反复重排
例如新列表 [b,a,d,c] 对应位置数组 [1,0,3,2]，其 LIS 可能是 [0,2]（对应新索引 1 和 3），意味着 a 和 c 可保位，b 和 d 需调整位置。
不复杂但容易忽略：LIS 在这里不是为了排序，而是为了识别“顺序保真度”最高的节点链——它是 Vue 在响应式更新中兼顾性能与准确性的关键数学支点。
