不太理解节点移动

其实课程视频中讲解的diff是个简版。vue3虚拟DOM的最后一个版本中关于新旧虚拟DOM是数组的情况，采取的快速比对 + 最长递增序列来实现的。

这个最长递增序列的本质是确定哪些老节点不需要移动，而官方实现的这个函数内部还采取了贪心+二分查找+前驱节点追溯让序列正确，

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) >> 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
      }
    }
  }
  u = result.length
  v = result[u - 1]
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }
  return result
}

不知道老师是否理解上面的逻辑思想

function getSequence(arr: number[]): number[] {
  // p 数组用于存储每个元素的前驱节点索引，以便最后回溯还原出正确的递增序列
  const p = arr.slice()
  // result 存储的是最长递增子序列在原数组中的【索引】，初始化先放入第一个索引 0
  const result = [0]
  let i, j, u, v, c
  const len = arr.length

  for (i = 0; i < len; i++) {
    const arrI = arr[i]
    // 0 在 Vue3 的 diff 中表示这是一个全新的节点（没有对应的旧节点），不需要参与最长递增序列的计算，直接跳过
    if (arrI !== 0) {
      j = result[result.length - 1]
      
      // 1. 贪心策略（快速路径）
      // 如果当前元素大于 result 序列末尾索引对应的元素，说明递增关系成立，直接将其索引追加到 result 末尾
      if (arr[j] < arrI) {
        p[i] = j // 记录当前节点追加时的前驱节点索引
        result.push(i)
        continue
      }
      
      // 2. 二分查找
      // 如果当前元素比 result 末尾的元素小，我们需要在 result 中找到第一个大于等于当前元素的位置，并将其替换。
      // 这里的核心贪心思想是：让序列中的元素尽可能小，这样后续才更有可能接上更多的元素。
      u = 0
      v = result.length - 1
      while (u < v) {
        c = (u + v) >> 1 // 位运算，等同于 Math.floor((u + v) / 2)
        if (arr[result[c]] < arrI) {
          u = c + 1
        } else {
          v = c
        }
      }
      
      // 找到了替换位置 u。只有当 arrI 严格小于该位置的元素时，才执行替换操作
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1] // 关键步骤：在替换前，将其前驱节点指向替换位置的前一个节点
        }
        result[u] = i // 替换该位置的索引。注意：这一步可能会导致 result 里的序列在真实数组中并不是真正的先后顺序
      }
    }
  }
  
  // 3. 前驱追溯（回溯修正）
  // 为什么需要修正？因为前面的二分替换虽然保证了 result 长度（最长递增子序列的长度）是正确的，
  // 但替换操作可能破坏了元素在原数组中的真实先后顺序。
  // 不过，result 的最后一个元素肯定是正确的（因为它要么是真实追加的，要么是替换后形成的有效末尾）。
  u = result.length
  v = result[u - 1] // 从 result 的最后一个正确索引开始倒推
  
  // 根据 p 数组记录的真实前驱关系，从后往前遍历，强行修正 result 数组
  while (u-- > 0) {
    result[u] = v
    v = p[v] // 不断找自己的上一个“老祖宗”
  }
  
  // 返回修正后的最长递增子序列索引数组，这些索引对应的老节点在 Vue 更新时可以直接跳过移动操作
  return result
}

上面是AI代码注释，我看了一下。

你发的是源码吗？我没有扒这一块。我主要是对照着《vue3源码解析》读了一下。

贪心思想，假设我们有个数组 [2, 1, 5, 3, 6, 4, 8, 9, 7]  我们要找最长递增。

当我们碰到 1 的时候，用 1 替换掉 result 里的 2 是稳赚不赔的，因为 1 比 2 小，后面接上大数字的概率更高。

二分查找，为了找到这个“该被替换的位置”，如果用普通的 for 循环找，时间复杂度会退化到 $O(n^2)$。

Vue 在这里使用了二分查找，将整体时间复杂度优化到了 $O(n \log n)$，这在处理大量 DOM 节点时性能提升巨大。

前驱追溯（修正序列）

这是最难理解但也最巧妙的一步：

• 假设原数组是 [2, 3, 4, 1]。

• 走到 4 的时候，result 存的索引对应的数字是 [2, 3, 4]。

• 走到 1 的时候，二分查找会把 2 替换掉，变成 [1, 3, 4]。

• 原数组中 1 是在 3 和 4 后面的，[1, 3, 4] 这个序列在原数组中根本不存在！

  虽然 result 里面的序列乱了，但 result 的 长度 是永远正确的，且 result 的 最后一个元素 肯定是正确的（因为它是真实追加进去的，或者是能连接最长链路的节点）。所以，我们通过 p 数组记录每次产生链接时的前驱节点，最后从最后一个节点开始倒推，就能还原出一条绝对正确的、真实存在于原数组中的最长递增序列。

是的，课程代码