一、先搞懂：最长递增子序列（LIS）是什么？
最长递增子序列（Longest Increasing Subsequence，简称 LIS）是动态规划/贪心+二分领域的经典算法问题，核心是找一个数组中「元素严格/非严格递增、且不要求连续」的最长子序列。
1. 核心概念（通俗举例）
- 子序列：数组中挑出部分元素（顺序不变，可间隔），比如
[10,9,2,5,3,7,101,18]的子序列可以是[2,5,7,101]； - 递增：子序列中后一个元素 > 前一个（严格递增，也可定义为 ≥ 非严格）；
- LIS：满足递增的最长子序列，比如上面数组的 LIS 长度是 4（
[2,3,7,101]或[2,5,7,101]）。
2. 两种核心解法（重点讲 Vue3 用的高效版）
| 解法 | 时间复杂度 | 核心思路 |
|---|---|---|
| 动态规划（DP） | O(n²) | 用dp[i]表示以第 i 个元素结尾的 LIS 长度，遍历每个元素对比前面所有元素更新 dp |
| 贪心+二分 | O(n log n) | 维护一个“最小末尾数组”，用二分找替换位置，数组长度就是 LIS 长度（Vue3 用这个） |
贪心+二分 通俗示例（比如数组[2,5,3,7,11,8,10,13,6]）
- 初始化空数组
tails = []； - 遍历每个元素：
- 2：tails 空，直接加 →
[2]； - 5：比 tails 最后一个大，加 →
[2,5]； - 3：比 5 小，找 tails 中第一个 ≥3 的位置（索引1），替换 5 →
[2,3]； - 7：比 3 大，加 →
[2,3,7]； - 11：加 →
[2,3,7,11]； - 8：替换 11 →
[2,3,7,8]； - 10：替换 8 →
[2,3,7,10]； - 13：加 →
[2,3,7,10,13]； - 6：替换 7 →
[2,3,6,10,13]；
- 2：tails 空，直接加 →
- 最终 tails 长度 5，就是 LIS 长度（注意 tails 不是真正的 LIS，只是长度相等）。
二、Vue3 中是否用到 LIS？—— 不仅用了，还很关键！
Vue3 在虚拟 DOM 的 diff 算法中，核心使用了 LIS 算法优化「列表更新时的 DOM 移动逻辑」，是提升 diff 性能的关键。
1. 为什么需要 LIS？（背景）
当 Vue 渲染列表（比如v-for）且节点有key时，更新列表（比如增删、排序）需要对比「老 vnode 数组」和「新 vnode 数组」，核心目标是：最小化 DOM 操作（少移动、少删除/新增）。
比如老列表：[a, b, c, d]（key 对应），新列表：[b, d, a, c]。如果直接暴力更新，会大量移动 DOM；但如果找到「不需要移动的最长节点序列」，只移动其他节点，就能大幅减少操作。
2. Vue3 中 LIS 的具体应用流程
Vue3 的patchChildren方法（处理子节点更新）中，针对「新老节点都是数组且有 key」的场景，核心步骤：
步骤1：建立映射，筛选“可复用节点”
- 遍历新节点数组，记录「key → 新节点索引」的映射；
- 遍历老节点数组，找到“新数组中也存在的节点”，生成一个
source数组：source[i] = 新数组中该老节点的索引（不存在则为 -1）。
举例：
- 老节点：
[a(key:a), b(key:b), c(key:c), d(key:d)] - 新节点：
[b(key:b), d(key:d), a(key:a), c(key:c)] - source 数组：
[2, 0, 3, 1]（a 在新数组索引 2，b 在 0，c 在 3，d 在 1）。
步骤2：计算 source 数组的 LIS（关键！）
上面的 source 数组[2,0,3,1]，其严格递增的 LIS是[0,1]（对应老节点 b、d）或[2,3]（对应 a、c）—— 这个 LIS 对应的老节点，就是「不需要移动的最长序列」。
步骤3：基于 LIS 最小化 DOM 移动
Vue3 会从后往前遍历新节点，结合 LIS 结果：
- LIS 中的节点：位置已经“天然有序”，无需移动；
- 非 LIS 中的节点：只需要移动到目标位置，而非删除重建。
3. 为什么用 LIS？
因为 LIS 是「最长的无需移动序列」，能最大程度减少 DOM 操作次数（DOM 移动是高性能开销操作），把 diff 算法的时间复杂度从 O(n²) 优化到 O(n log n)，这也是 Vue3 diff 比 Vue2 更高效的核心原因之一。
4. Vue3 中 LIS 的源码位置
核心代码在runtime-core/src/patchChildren.ts中的getSequence函数（就是贪心+二分实现的 LIS），简化版核心逻辑如下：
// Vue3 源码中 getSequence 函数（简化版）functiongetSequence(arr){constlen=arr.length;constresult=[0];// 存储 LIS 的索引（不是值）constp=newArray(len).fill(0);// 记录前驱节点，用于还原完整 LISletlastIndex;letstart,end,mid;for(leti=0;i<len;i++){constval=arr[i];lastIndex=result[result.length-1];if(val>arr[lastIndex]){p[i]=lastIndex;result.push(i);continue;}// 二分找替换位置start=0;end=result.length-1;while(start<end){mid=(start+end)>>1;if(arr[result[mid]]<val){start=mid+1;}else{end=mid;}}if(val<arr[result[start]]){if(start>0){p[i]=result[start-1];}result[start]=i;}}// 还原完整的 LIS 索引leti=result.length;letlast=result[i-1];while(i--){result[i]=last;last=p[last];}returnresult;}三、总结
- 最长递增子序列（LIS）是找数组中「最长递增非连续子序列」的算法，Vue3 用的是 O(n log n) 的贪心+二分实现；
- Vue3 在列表 diff 算法中核心依赖 LIS：通过计算可复用节点索引数组的 LIS，找到“无需移动的最长节点序列”，最小化 DOM 操作，提升更新性能；
- 这是 Vue3 对比 Vue2 diff 算法的重要优化点（Vue2 未用 LIS，diff 时间复杂度更高）。
