前言学完 Vue3 Diff 头尾双指针、乱序 Map 复用、倒序插入后卡在最后一个核心难点最长递增子序列 LIS。最大的疑惑永远是这两个节点明明已经patch 复用更新完了为什么还要移动 DOMLIS 到底优化了什么不加 LIS 代码不也能跑吗本文结合 Vue3 真实 Diff 流程、完整案例、源码对照彻底讲透 LIS看完直接搞定面试高频考点。一、先理清 Diff 两个核心误区1. patch 只更新内容不更新位置乱序 Diff 中patch(n1, n2, el)只做三件事复用旧 DOM 节点更新属性、文本、子节点不会改变 DOM 在页面中的排列顺序也就是说内容是新的站位还是旧的。2. VNode 顺序 ≠ DOM 顺序新 VNode 数组是 JS 对象顺序是理想的新顺序但真实 DOM 是物理渲染节点会停留在旧顺序。想要 DOM 和 VNode 顺序一致必须手动移动 DOM。二、没有 LIS 的 Diff 有什么问题我们之前手写的简易 Diff逻辑是所有复用节点全部统一移动一遍哪怕有些节点相对顺序根本没变、完全不需要动也会被强制执行hostInsert造成多余 DOM 操作性能浪费。举个真实案例旧节点[a, b, c, d, e]新节点[a, b, e, c, f, d]头尾比对后乱序区间旧乱序[c, d, e]新乱序[e, c, f, d]最终生成复用标记数组newIndexToOldMap [4, 3, 0, 5]剔除新增节点 0得到新列表对应的旧下标序列[4, 3, 5]简易版 Diff无 LISe、c、d 三个复用节点全部移动三次 DOM 操作。Vue3 完整版 Diff有 LIS找出无需移动的节点只移动必须动的节点仅一次 DOM 操作。三、LIS 核心原理最长递增子序列 找出乱序中「相对顺序完全正确、无需移动」的最大节点集合。递增 旧下标越来越大 节点相对位置没变 无需移动。案例推演序列[4, 3, 5]最长递增子序列为[3, 5]对应节点c、d这两个节点在新旧列表中相对顺序一致原地不动。只有 e 节点顺序错乱仅移动 e 即可。优化结果3次DOM移动 → 1次DOM移动四、LIS 在 Diff 中的完整执行流程结合 Vue3 源码LIS 优化插在「标记数组生成后、倒序移动前」。步骤1生成旧下标映射序列根据newIndexToOldMap剔除 0新增节点得到纯复用节点的旧下标序列。步骤2贪心二分求 LISVue3 采用 O(nlogn) 算法快速算出最长递增子序列得到无需移动的节点下标。步骤3倒序遍历跳过稳定节点这是 Vue3 源码原版最长递增子序列函数采用贪心二分性能最优倒序遍历新节点在 LIS 中跳过不移动不在 LIS 中执行 hostInsert 移动位置标记为 0新增节点直接挂载五、Vue3 源码 LIS 算法实现// Vue3 源码原版贪心二分 求最长递增子序列下标O(nlogn) // 作用接收新节点对应的旧下标序列返回【无需移动的节点下标集合】 // 核心只保留相对顺序不变的稳定节点最大程度减少 DOM 移动 function getSequence(arr) { // p 数组记录每个节点的【前驱节点下标】用于最后回溯还原完整 LIS 路径 const p arr.slice() // result 数组贪心过程存储的 LIS 下标初始默认第一个元素为起始节点 const result [0] // 声明循环变量 let i, j, u, v, c const len arr.length // 遍历整个下标序列贪心构建最长递增子序列 for (i 0; i len; i) { // 当前遍历的节点对应的旧数组下标 const arrI arr[i] // 过滤 00 代表新增节点无需参与 LIS 计算无旧 DOM 可复用 if (arrI ! 0) { // 获取当前 LIS 末尾节点的下标 j result[result.length - 1] // 情况1当前值大于 LIS 末尾值满足递增 // 直接追加到 LIS 末尾更新前驱节点 if (arrI arr[j]) { p[i] j result.push(i) continue } // 情况2当前值不大于末尾值二分查找替换位置贪心优化让序列更“小”后续更容易更长 u 0 v result.length // 二分查找找到第一个大于当前值的位置 while (u v) { // 位运算等价于 Math.floor((u v) / 2) c (u v) 1 if (arr[result[c]] arrI) u c 1 else v c } // 替换找到的位置维持递增序列的最小末尾值 if (arrI arr[result[u]]) { // 记录当前节点的前驱节点 if (u 0) p[i] result[u - 1] // 替换贪心序列对应位置优化后续遍历 result[u] i } } } // 回溯 p 前驱数组还原出【完整、真实的最长递增子序列下标】 // 前面贪心得到的 result 只是长度最优路径不完整需要回溯修正 u result.length v result[u - 1] while (u-- 0) { result[u] v v p[v] } // 返回结果所有无需移动的节点【相对下标】集合 return result }返回值无需移动的节点下标集合六、加入 LIS 后的完整 Diff 移动逻辑// 得到无需移动的节点下标 const lis getSequence(newIndexToOldMap) // 存储是否是稳定节点无需移动 const isStable new Set(lis) // 倒序遍历新节点新增 / 按需移动 for (let i toBePatched - 1; i 0; i--) { const newIndex s2 i; const n2 c2[newIndex]; const anchor c2[newIndex 1]?.el || null; if (newIndexToOldMap[i] 0) { // 全新节点挂载 patch(null, n2, el, anchor); } else { // LIS 优化稳定节点直接跳过不移动 if(!isStable.has(i)){ hostInsert(n2.el, el, anchor); } } }