最长递增子序列
实现 LIS 算法，理解 Vue3 Diff 中的节点移动优化
问题
实现最长递增子序列（LIS）算法，并理解它在 Vue3 Diff 中的应用。
给定数组 [10, 9, 2, 5, 3, 7, 101, 18]，最长递增子序列是 [2, 3, 7, 18] 或 [2, 3, 7, 101]，长度为 4。
解答
方法一：动态规划 O(n²)
function lengthOfLIS(nums) {
if (nums.length === 0) return 0
// dp[i] 表示以 nums[i] 结尾的最长递增子序列长度
const dp = new Array(nums.length).fill(1)
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
// 如果 nums[i] 大于 nums[j]，可以接在后面
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1)
}
}
}
return Math.max(...dp)
}
console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])) // 4方法二：贪心 + 二分查找 O(n log n)
function lengthOfLIS(nums) {
if (nums.length === 0) return 0
// tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素
const tails = []
for (const num of nums) {
// 二分查找 num 应该插入的位置
let left = 0
let right = tails.length
while (left < right) {
const mid = (left + right) >> 1
if (tails[mid] < num) {
left = mid + 1
} else {
right = mid
}
}
// 替换或追加
tails[left] = num
}
return tails.length
}Vue3 中的实现：获取 LIS 的索引
Vue3 需要的不是长度，而是最长递增子序列的索引数组，用于确定哪些节点不需要移动。
// Vue3 源码简化版
function getSequence(arr) {
const p = arr.slice() // 用于回溯的前驱索引数组
const result = [0] // 存储 LIS 的索引
for (let i = 0; i < arr.length; i++) {
const current = arr[i]
// Vue3 中 0 表示新增节点，跳过
if (current !== 0) {
const lastIndex = result[result.length - 1]
// 当前值大于 result 最后一个对应的值，直接追加
if (arr[lastIndex] < current) {
p[i] = lastIndex // 记录前驱索引
result.push(i)
continue
}
// 二分查找，找到第一个 >= current 的位置
let left = 0
let right = result.length - 1
while (left < right) {
const mid = (left + right) >> 1
if (arr[result[mid]] < current) {
left = mid + 1
} else {
right = mid
}
}
// 替换
if (current < arr[result[left]]) {
if (left > 0) {
p[i] = result[left - 1] // 记录前驱索引
}
result[left] = i
}
}
}
// 回溯，得到正确的 LIS 索引序列
let len = result.length
let idx = result[len - 1]
while (len-- > 0) {
result[len] = idx
idx = p[idx]
}
return result
}
// 测试
console.log(getSequence([2, 3, 1, 5, 6, 8, 7, 9, 4]))
// [0, 1, 3, 4, 6, 7] 对应值 [2, 3, 5, 6, 7, 9]Vue3 Diff 中的应用
// 简化的 Vue3 diff 逻辑
function patchKeyedChildren(oldChildren, newChildren) {
// 1. 预处理：头部相同节点
// 2. 预处理：尾部相同节点
// 3. 处理中间乱序部分
// 假设中间部分新节点在旧节点中的索引为：
const newIndexToOldIndexMap = [5, 3, 4, 0] // 0 表示新增
// 获取最长递增子序列的索引
const increasingNewIndexSequence = getSequence(newIndexToOldIndexMap)
// 结果: [1, 2] 对应值 [3, 4]，这些节点不需要移动
// 倒序遍历新节点
let j = increasingNewIndexSequence.length - 1
for (let i = newIndexToOldIndexMap.length - 1; i >= 0; i--) {
if (newIndexToOldIndexMap[i] === 0) {
// 新增节点，执行 mount
} else if (j < 0 || i !== increasingNewIndexSequence[j]) {
// 不在 LIS 中，需要移动
// 执行 move 操作
} else {
// 在 LIS 中，不需要移动
j--
}
}
}关键点
- LIS 作用：找出不需要移动的最长节点序列，最小化 DOM 操作
- 贪心思想：维护一个递增的 tails 数组，每个位置存储该长度子序列的最小末尾
- 二分查找：在 tails 中找到当前元素应该替换的位置，保证 O(log n) 复杂度
- 回溯技巧：Vue3 用前驱数组 p 记录路径，最后回溯得到正确的索引序列
- 倒序遍历：Vue3 倒序处理是为了使用
insertBefore时锚点节点已经就位
目录