最长递增子序列算法

一句话概括

最长递增子序列（LIS） 是一个「找出序列中保持递增的最长子序列（可不连续）」的经典算法。Vue 3 把它用在虚拟 DOM Diff 中，通过找到「不需要移动的节点的最长序列」，让列表重排时的 DOM 操作次数降到理论最低。

核心知识点

1. LIS 的 O(n²) DP 解法

定义 dp[i] 为以第 i 个元素结尾的 LIS 长度。对每个 i，回头看所有 j < i，如果 nums[j] < nums[i] 且 dp[j] + 1 > dp[i]，就更新。

function lengthOfLIS(nums: number[]): number {
  const dp = new Array(nums.length).fill(1);
  let max = 1;
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    max = Math.max(max, dp[i]);
  }
  return max;
}

lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]); // 4 → [2,3,7,101]

2. O(n log n) 贪心 + 二分

维护一个 tails 数组，tails[i] 表示长度为 i+1 的递增子序列的最小末尾值。tails 天然严格递增，所以可以用二分查找每个新元素该放哪里——替换老的末尾或追加。

function lengthOfLIS(nums: number[]): number {
  const tails: number[] = [];
  for (const num of nums) {
    let l = 0, r = tails.length;
    while (l < r) {
      const m = (l + r) >> 1;
      if (tails[m] < num) l = m + 1;
      else r = m;
    }
    if (l === tails.length) tails.push(num);
    else tails[l] = num;
  }
  return tails.length;
}

为什么替换不破坏结果？ tails 存的不是真实的 LIS 序列，而是「各长度 LIS 的最优末尾」。3 被 1 替换后，长度 1 的末尾更小了，后续元素更容易接上去形成更长序列。这就是贪心的精髓：始终保留当前最优的潜力。

3. 带回溯的完整 LIS（Vue 3 同款）

Diff 算法不光要长度，还要具体哪些索引不动。需要前驱数组 p 记录每个元素在 LIS 中的前一个位置，最后回溯重建。

function getSequence(arr: number[]): number[] {
  const p = arr.slice();
  const result = [0]; // tails 存索引，不是值

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === 0) continue; // 新节点跳过
    const j = result[result.length - 1];
    if (arr[j] < arr[i]) {
      p[i] = j;
      result.push(i);
      continue;
    }
    let l = 0, r = result.length - 1;
    while (l < r) {
      const m = (l + r) >> 1;
      if (arr[result[m]] < arr[i]) l = m + 1;
      else r = m;
    }
    if (arr[i] < arr[result[l]]) {
      if (l > 0) p[i] = result[l - 1];
      result[l] = i;
    }
  }

  // 回溯重建
  let len = result.length;
  let idx = result[len - 1];
  while (len-- > 0) {
    result[len] = idx;
    idx = p[idx];
  }
  return result;
}

4. LIS 在 Vue 3 Diff 中怎么用

Diff 五个阶段：头同步 → 尾同步 → 纯增删判断 → 构建 key→index 映射 → LIS 决定最小移动。

旧列表: [A, B, C, D, E]
新列表: [A, B, E, C, D]

去头尾后剩余：
旧: [C, D, E]  新: [E, C, D]
位置数组（旧节点在新列表中的位置）: [1, 2, 0]  → LIS: [1, 2]
即 C 和 D 相对顺序没变 → 不动它们，只把 E 移到 C 前面。3 个元素只动 1 个。

核心洞察：LIS 里的节点的相对顺序在新旧列表中一致，天然不需要移动。 LIS 越长，DOM 操作越少。

5. 为什么 React 不用 LIS？

React Fiber 用单向链表 Diff（单边遍历 + 移动标记），不追求「最小移动次数」。React 团队认为：LIS 的 O(n log n) 计算本身有开销，而 DOM 的 insertBefore 在现代浏览器里已经很快了，多移动几个节点几乎无感。两条路线的取舍：Vue 用 JS 算力换 DOM 操作的极致少，React 接受多一些 DOM 操作来精简 Diff 逻辑。

「其实你每天都在用」

1. v-for 列表重排：拖拽排序、表格按列排序时，Vue 3 内部就在跑 LIS，你无感但性能受益。
2. Git diff 算法：git diff 的 patience diff 算法就是 LIS 的思想来源——找到两版文件中「唯一匹配行」的最长递增子序列来对齐。
3. 协同编辑冲突解决：Google Docs 的 OT/CRDT 算法中，找到两个用户修改之间的「共识序列」本质也是 LIS。
4. 表格 / 瀑布流懒加载后的重排：滚动加载更多、虚拟列表数据刷新时，Diff 算法都在用 LIS 决定哪些 DOM 节点复用。
5. 二分查找无处不在：LIS 的 O(n log n) 实现本身就是对「二分 + 贪心」的经典运用，刷完 LIS 再去看 lower_bound / upper_bound 会豁然开朗。

常见误解（FAQ）

❌ 误区：LIS 就是找到能保持不动的最长子数组（连续）。 LIS 里的 “S” 是 Subsequence（子序列），不是 Subarray（子数组），不要求连续。[2, 5, 3, 7] 的 LIS 是 [2, 5, 7] 或 [2, 3, 7]，跳过了位置不相邻的元素。

❌ 误区：tails 数组的最终结果就是 LIS。 tails 只存各长度的最优末尾，经过替换后内容不再是真正的 LIS 序列。需要前驱数组 p 回溯才能还原。面试里被问「tails 为什么不是最终答案」是很常见的 follow-up。

❌ 误区：没有 key 的时候 Vue 也会用 LIS。 没有 key 时 Vue 走 patchUnkeyedChildren——按索引就地复用，O(n) 搞定，但不保证正确性（元素被错误复用）。LIS 只在 patchKeyedChildren 路径中使用，前提是有稳定的 key。

❌ 误区：Vue 3 Diff 就是「双向比较 + LIS」。 Vue 3 头部尾部的预处理是单向的（新 vs 旧），不是 Vue 2 那种四路双端比较（新头旧头、新尾旧尾、新头旧尾、新尾旧头）。Vue 3 的策略更简洁：两边向中间收拢，中间乱序部分交给 LIS。

一句话总结

LIS 在 Vue 3 Diff 中的应用是「把经典算法落到工程实践」的教科书级案例——它不是炫技，而是真实地把列表重排的 DOM 操作次数降到了理论下界。