Vue3 diff 算法之：最长递增子序列

最长递增子序列动态规划的解法在其他博客列些，感兴趣的可以看这里动态规划：最长递增子序列

动态规划的算法复杂度是O(n^2)，效率会稍微慢一些，但是相对来说比较好理解。

Vue3 的 diff 算法恰好符合 LeetCode 300. 最长递增子序列 这道题最后一个要求：

你能将算法的时间复杂度降低到 O(n log(n)) 吗?

一、Vue3 为什么需要最长递增子序列？

假设我们有 1,2,3,4,5 五个同级节点，经过移动后变成了 1,3,4,5,2。

• 我们肉眼容易看是 2 节点移动到了最后，但是如果没有最长递增子序列的概念，我们就认为是 除了 1，其他都有位置移动。
• 如果我们引入最长递增子序列的概念，我们就认为是 1,3,4,5 这四个节点是最长的递增子序列，2 节点只是在这个子序列的末尾。
• dom 操作的时候只需要做一次移动，而不是四次。

最终移动 dom 节点的核心代码:

//移动后， 由于 2 是最后一个节点，anchorNode 为 null 默认插入最后
parentNode.insertBefore(2,  null)

二、Vue3 实现最长递增子序列

Vue3 的 diff 算法是通过贪心算法 + 二分查找 + 前驱节点记录来实现的。

• 贪心算法：只要当前遍历的数据比前一个大，加入结果数组，记录前驱节点
• 二分查找：在当前结果数组中查找比当前数据小的元素，替代当前数据，记录前驱节点

让我们模拟贪心和二分算法实现：

遍历移动后数组 [1, 3, 4, 5，2] 放入结果数组用于求最长子序列
[1]
[1, 3]
[1, 3, 4]
[1, 3, 4, 5]
[1, 2, 4, 5]

我们可以看到计算出来的结果长度是正确的，但是正确答案是 [1, 3, 4, 5]，而我们得到的结果是 [1, 2, 4, 5]。

• 贪心算法：只要当前遍历的数据比前一个大，加入结果数组，结果数组是 [1, 3, 4, 5]，但是 2 节点并不在正确答案中，我们需要辅助数组 p 来记录前驱节点。

遍历移动后数组 [1, 3, 4, 5，2] 放入结果数组用于求最长子序列
[1] p=[0]
[1, 3]  p=[0,0] 3的前驱节点是 索引0
[1, 3, 4] p=[0,0,1] 4的前驱节点是 索引1
[1, 3, 4, 5] p=[0,0,1,2] 5的前驱节点是 索引2
[1, 2, 4, 5] p=[0,0,1,2,0] 2的前驱节点是 索引0

我们能确定的是，结果数组最后一个元素一定是正确的，因为它是最长的递增子序列。

我们根据 p 数组，倒推出正确的结果数组。

数组：[1, 3, 4, 5，2]
结果数组：[1, 3, 4, 5]
p 数组：[0, 0, 1, 2, 0]

遍历结果数组：
最后一个是 5, 对应的前驱索引是 2，记下一个是 4
倒推：
[4,5] 4的前驱节点是 索引1
[3,4,5]
[1,3,4,5] 得到正确答案

让我们来看看 Vue3 的实现：

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++) {
    //arrI 第 i 个
    const arrI = arr[i];
    // 如果是 0 表示新增节点
    if (arrI !== 0) {
      // 取出上一个结果的最后一个元素 第一次是 0
      j = result[result.length - 1];
      // 如果最后一个都是小于 arrI 的话，索引直接加入
      if (arr[j] < arrI) {
        // 记录前驱节点
        p[i] = j;
        // arrI 更大，直接加入结果数组
        result.push(i);
        // 后面步骤是二分法，只有 arrI 比 result[u] 小才更新
        continue;
      }
      // 结果数组的开始结束索引
      u = 0;
      v = result.length - 1;
      // 这和索引的二分法类似，只不过这里是数组元素
      while (u < v) {
        // 二分法查找插入位置 位运算右移，相当于 Math.floor((u + v) / 2)
        c = (u + v) >> 1;
        if (arr[result[c]] < arrI) {
          // 如果 arrI 还要大于当前中点，左边界往右收窄
          u = c + 1;
        } else {
          // 右边界往左收窄
          v = c;
        }
      }
      // 找到小于 arrI 的第一个元素的索引
      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;
}

TODO：补充图解