观感度：????????????????????
口味：辣炒花蛤
烹饪工夫：10min
本文已收录在前端食堂同名仓库 Github github.com/Geekhyt，欢迎光临食堂，如果感觉酒菜还算可口，赏个 Star 对食堂老板来说是莫大的激励。
想要搞明确 Vue3 的 DOM Diff 外围算法，咱们要从一道 LeetCode 真题说起。
咱们先来一起读读题：
LeetCode 真题 300. 最长回升子序列
给定一个无序的整数数组，找到其中最长回升子序列的长度。
示例：
输出: [10,9,2,5,3,7,101,18]
输入: 4
解释: 最长的回升子序列是 [2,3,7,101]，它的长度是 4。
阐明：
- 可能会有多种最长回升子序列的组合，你只须要输入对应的长度即可。
- 你算法的工夫复杂度应该为 O(n2)。
进阶: 你能将算法的工夫复杂度升高到 O(nlogn) 吗?
读题完结。
什么是回升子序列？
首先，咱们须要对根本的概念进行理解和辨别：
- 子串：肯定是间断的
- 子序列：子序列不要求间断 例如：[6, 9, 12] 是 [1, 3, 6, 8, 9, 10, 12] 的一个子序列
- 回升 / 递增子序列：肯定是严格回升 / 递增的子序列
留神：子序列中元素的绝对程序必须放弃在原始数组中的绝对程序
题解
动静布局
对于动静布局的思维，还不理解的同学们能够移步我的这篇专栏入个门，「算法思维」分治、动静布局、回溯、贪婪一锅炖
咱们能够将状态 dp[i] 定义为以 nums[i] 这个数结尾 (肯定包含 nums[i]) 的最长递增子序列的长度，并将 dp[i] 初始化为 1，因为每个元素都是一个独自的子序列。
定义状态转移方程：
- 当咱们遍历
nums[i]时，须要同时对比曾经遍历过的nums[j] - 如果
nums[i] > nums[j]，nums[i]就能够退出到序列nums[j]的最初，长度就是dp[j] + 1
注：(0 <= j < i) (nums[j] < nums[i])
const lengthOfLIS = function(nums) {
let n = nums.length;
if (n == 0) {return 0;}
let dp = new Array(n).fill(1);
for (let i = 0; i < n; i++) {for (let j = 0; j < i; j++) {if (nums[j] < nums[i]) {dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Math.max(...dp)
}- 工夫复杂度：O(n^2)
- 空间复杂度：O(n)
这里我画了一张图，便于你了解。
贪婪 + 二分查找
对于贪婪和二分查找还不理解的同学们能够移步我的这两篇专栏入个门。
- 「算法思维」分治、动静布局、回溯、贪婪一锅炖
- 从酒桌游戏看二分查找算法
这里再联合本题了解一下贪婪思维，同样是长度为 2 的序列，[1,2] 肯定比 [1,4] 好，因为它更有后劲。换句话说，咱们想要组成最长的递增子序列，
就要让这个子序列中回升的尽可能的慢，这样能力更长。
咱们能够创立一个 tails 数组，用来保留最长递增子序列，如果以后遍历的 nums[i] 大于 tails 的最初一个元素 (也就是 tails 中的最大值) 时，咱们将其追加到前面即可。否则的话，咱们就查找 tails 中第一个大于 nums[i] 的数并替换它。因为是枯燥递增的序列，咱们能够应用二分查找，将工夫复杂度升高到 O(logn)。
const lengthOfLIS = function(nums) {
let len = nums.length;
if (len <= 1) {return len;}
let tails = [nums[0]];
for (let i = 0; i < len; i++) {// 以后遍历元素 nums[i] 大于 前一个递增子序列的 尾元素时，追加到前面即可
if (nums[i] > tails[tails.length - 1]) {tails.push(nums[i]);
} else {// 否则，查找递增子序列中第一个大于以后值的元素，用以后遍历元素 nums[i] 替换它
// 递增序列，能够应用二分查找
let left = 0;
let right = tails.length - 1;
while (left < right) {let mid = (left + right) >> 1;
if (tails[mid] < nums[i]) {left = mid + 1;} else {right = mid;}
}
tails[left] = nums[i];
}
}
return tails.length;
};- 工夫复杂度：O(nlogn)
- 空间复杂度：O(n)
这里我画了一张图，便于你了解。
留神：这种形式被替换后组成的新数组不肯定是解法一中正确后果的数组，但长度是一样的，不影响咱们对此题求解。
比方这种状况：[1,4,5,2,3,7,0]
tails = [1]tails = [1,4]tails = [1,4,5]tails = [1,2,5]tails = [1,2,3]tails = [1,2,3,7]tails = [0,2,3,7]
咱们能够看到最初 tails 的长度是正确的，然而外面的值不正确，因为最初一步的替换毁坏了子序列的性质。
Vue3 DOM Diff 外围算法
搞清楚了最长递增子序列这道算法题，咱们再来看 Vue3 的 DOM Diff 外围算法就简略的多了。
我晓得你曾经急不可待了，然而这里还是要插一句，如果你还不理解 React 以及 Vue2 的 DOM Diff 算法能够移步这个链接进行学习，循序渐进的学习能够让你更好的了解。
- Vue.js 技术揭秘
回来后咱们思考一个问题：Diff 算法的目标是什么？
为了缩小 DOM 操作的性能开销，咱们要尽可能的复用 DOM 元素。所以咱们须要判断出是否有节点须要挪动，应该如何挪动以及找出那些须要被增加或删除的节点。
好了，进入本文的正题，Vue3 DOM Diff 外围算法。
首先咱们要搞清楚，外围算法的的地位。外围算法其实是当新旧 children 都是多个子节点的时候才会触发。
上面这段代码就是 Vue3 的 DOM Diff 外围算法，我加上了在源码中的门路，不便你查找。
// packages/runtime-core/src/renderer.ts
function getSequence(arr: number[]): number[] {const p = arr.slice()
const result = [0]
let i, j, u, v, c
const len = arr.length
for (i = 0; i < len; i++) {const arrI = arr[i]
if (arrI !== 0) {j = result[result.length - 1]
if (arr[j] < arrI) {p[i] = j
result.push(i)
continue
}
u = 0
v = result.length - 1
while (u < v) {c = ((u + v) / 2) | 0
if (arr[result] < arrI) {u = c + 1} else {v = c}
}
if (arrI < arr[result[u]]) {if (u > 0) {p[i] = result[u - 1]
}
result[u] = i
}
}
}
u = result.length
v = result[u - 1]
while (u-- > 0) {result[u] = v
v = p[v]
}
return result
}getSequence 的作用就是找到那些不须要挪动的元素，在遍历的过程中，咱们能够间接跳过不进行其余操作。
其实这个算法的核心思想就是咱们下面讲到的求解最长递增子序列的第二种解法，贪婪 + 二分查找法。这也是为什么不焦急说它的起因，因为如果你看懂了下面的 LeetCode 题解，你就曾经把握了 Vue3 的 DOM Diff 外围算法的思维啦。
不过，想要搞懂每一行代码的细节，还需放到 Vue3 整个 DOM Diff 的上下文中去才行。而且须要留神的是，下面代码中的 getSequence 办法的返回值与 LeetCode 题中所要求的返回值不同，getSequence 返回的是最长递增子序列的索引。上文咱们曾提到过，应用贪婪 + 二分查找替换的形式存在一些 Bug，可能会导致后果不正确。Vue3 把这个问题解决掉了，上面咱们来一起看一下它是如何解决的。
// packages/runtime-core/src/renderer.ts
function getSequence(arr: number[]): number[] {const p = arr.slice() // 拷贝一个数组 p
const result = [0]
let i, j, u, v, c
const len = arr.length
for (i = 0; i < len; i++) {const arrI = arr[i]
// 排除等于 0 的状况
if (arrI !== 0) {j = result[result.length - 1]
// 与最初一项进行比拟
if (arr[j] < arrI) {p[i] = j // 最初一项与 p 对应的索引进行对应
result.push(i)
continue
}
// arrI 比 arr[j] 小，应用二分查找找到后替换它
// 定义二分查找区间
u = 0
v = result.length - 1
// 开启二分查找
while (u < v) {
// 取整失去以后地位
c = ((u + v) / 2) | 0
if (arr[result] < arrI) {u = c + 1} else {v = c}
}
// 比拟 => 替换
if (arrI < arr[result[u]]) {if (u > 0) {p[i] = result[u - 1] // 正确的后果
}
result[u] = i // 有可能替换会导致后果不正确，须要一个新数组 p 记录正确的后果
}
}
}
u = result.length
v = result[u - 1]
// 顺叙回溯 用 p 笼罩 result 进而找到最终正确的索引
while (u-- > 0) {result[u] = v
v = p[v]
}
return result
}Vue3 通过拷贝一个数组，用来存储正确的后果，而后通过回溯赋值的形式解决了贪婪 + 二分查找替换形式可能造成的值不正确的问题。
以上就是 Vue3 DOM Diff 的外围算法局部啦，欢迎光临前端食堂，客官您慢走～
❤️爱心三连击
1. 如果你感觉食堂酒菜还合胃口，就点个赞反对下吧，你的 赞是我最大的能源。
2. 关注公众号前端食堂，吃好每一顿饭！
3. 点赞、评论、转发 === 催更！