最长递增子序列怎样用贪心加二分做到 O(n log n)？Vue 3 的 diff 为什么用它？

简答

给一个数组 [10, 9, 2, 5, 3, 7, 101, 18]，从里面挑出一些数，顺序不变，而且严格递增，最多能挑几个？答案是 4，比如 2, 3, 7, 101。这就是最长递增子序列，LeetCode 300 题。

动态规划写法是 O(n²)。更快的做法用一个 tails 数组，tails[k] 记录“长度为 k+1 的递增子序列里，最小的结尾是多少”。结尾越小，后面越容易接上新的数。每来一个数，如果比 tails 里所有数都大，就追加到末尾，最长长度加 1；否则用二分找到第一个大于等于它的位置，把那里换成它。tails 始终是递增的，所以能二分，总共 O(n log n)。

要注意，tails 的长度是答案，但 tails 本身不一定是一个真实存在的子序列，因为替换会把后来的数放到前面。要还原出具体的子序列，得额外记一个数组，保存每个数接在谁后面，最后从末尾往回找。

Vue 3 的 diff 用的就是带还原的版本。列表中间乱序的部分，它把新节点在旧列表里的位置排成一个数组，求出最长递增子序列。这些节点之间的先后顺序没变，可以不动，只移动其余的节点，这样移动的次数最少。

只求长度

下面的 lengthOfLIS 只返回长度，二分用的是左闭右开区间。

function lengthOfLIS(nums) {
  const tails = [];
  for (const num of nums) {
    let left = 0;
    let right = tails.length;
    // 找第一个 >= num 的位置；用 >= 而不是 >，保证序列严格递增。
    while (left < right) {
      const mid = left + Math.floor((right - left) / 2);
      if (tails[mid] < num) left = mid + 1;
      else right = mid;
    }
    tails[left] = num;
  }
  return tails.length;
}

console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 4
console.log(lengthOfLIS([0, 1, 0, 3, 2, 3])); // 4
console.log(lengthOfLIS([7, 7, 7, 7])); // 1

拿第一组数据走一遍。10 进来，tails 是 [10]；9 比 10 小，替换，变成 [9]；2 替换，变成 [2]；5 追加，[2, 5]；3 替换 5，[2, 3]；7 追加，[2, 3, 7]；101 追加，[2, 3, 7, 101]；18 替换 101，[2, 3, 7, 18]。长度是 4。

为什么把 5 换成 3 不会出错？tails[1] 的意思是“长度为 2 的递增子序列，最小的结尾”。2, 5 和 2, 3 都是长度 2，但结尾 3 更小，后面来个 4 也能接上，所以留 3 更好。替换只是更新了“某个长度的最小结尾”，不会让已有的长度变短。

[7, 7, 7, 7] 为什么是 1？题目要求严格递增，相等的数不能接在一起。二分找的是第一个 >= num 的位置，第二个 7 会替换掉第一个 7，而不是追加。如果题目允许相等，要改成找第一个 > num 的位置，也就是《二分查找怎样定位时间轴边界？为什么重复值和空数组容易写错？》里 lowerBound 和 upperBound 的区别。

还原出具体的子序列

tails 存的是值，不能直接当答案。还原时改成存下标，同时用 prev[i] 记录第 i 个数接在哪个下标后面。

function getSequenceIndexes(nums) {
  const tails = []; // 存下标，tails[k] 是长度为 k+1 时结尾元素的下标
  const prev = new Array(nums.length).fill(-1);
  for (let i = 0; i < nums.length; i += 1) {
    let left = 0;
    let right = tails.length;
    while (left < right) {
      const mid = left + Math.floor((right - left) / 2);
      if (nums[tails[mid]] < nums[i]) left = mid + 1;
      else right = mid;
    }
    if (left > 0) prev[i] = tails[left - 1];
    tails[left] = i;
  }
  // 从最长序列的结尾往回找前驱。
  const result = [];
  let index = tails.length ? tails[tails.length - 1] : -1;
  while (index !== -1) {
    result.unshift(index);
    index = prev[index];
  }
  return result;
}

const nums = [10, 9, 2, 5, 3, 7, 101, 18];
const indexes = getSequenceIndexes(nums);
console.log(indexes.join(',')); // 2,4,5,7
console.log(indexes.map((i) => nums[i]).join(',')); // 2,3,7,18

每个数放进 tails[left] 时，它前面那一格 tails[left - 1] 就是它在递增序列里的前一个数，记到 prev 里。最后从 tails 的最后一项出发，沿着 prev 往回走，就得到一条真实的递增子序列 2, 3, 7, 18。

Vue 3 的 diff 怎样用它

Vue 3 比较新旧两组子节点时，先跳过开头和结尾相同的部分，剩下中间乱序的一段。它为这一段建一个数组 newIndexToOldIndexMap，每一项是这个新节点在旧列表里的位置加 1，填 0 表示这是新增的节点。

比如旧列表是 A B C D，新列表是 D A B C。按新顺序排，它们在旧列表里的位置是 3、0、1、2，其中 0、1、2 是递增的，说明 A B C 之间的先后顺序没变。所以 A B C 不用动，只把 D 移到最前面，一次移动就够了。

Vue 源码 packages/runtime-core/src/renderer.ts 里的 getSequence 就是上面这种“贪心加二分，再用前驱数组还原”的写法，返回的是下标；它会跳过值为 0 的项，因为新增的节点要新挂载，不参与移动。源码里还写着，只有检测到节点发生了移动，才计算最长递增子序列。双端比较和这种做法的对比见《Vue 2 的 diff 算法是怎样比较子节点的？》。

常见追问

为什么最长递增子序列能让移动次数最少？

不在子序列里的节点都要移动，在子序列里的可以不动。子序列越长，不用动的节点越多，要移动的就越少。所以找最长的那一条。

O(n²) 的动态规划写法还用掌握吗？

要能讲出来，它是理解这道题的基础：dp[i] 是以第 i 个数结尾的最长长度，等于前面所有比它小的数的 dp 最大值加 1。见《动态规划怎么入门？爬楼梯和最长递增子序列怎样做？》。