当 Vue 对比新旧两组列表节点时，目标是用最少的 DOM 操作完成更新：能复用的就复用，能移动的就移动，只有无法就地复用的才去创建或删除。对于没有 key 的简单列表，Vue 默认按顺序对比；但一旦加上 key，Diff 算法就会尝试最大化节点复用，避免不必要的销毁和重建——这时候，最长递增子序列就登场了。
问题背景：怎样移动最少的节点？
假设一个列表从 [A, B, C, D] 变成了 [D, A, B, C]。最简单的做法是把整个列表清空，然后按新顺序重建四个节点，成本很高。更聪明的做法是：看看哪些节点的相对顺序本来就和新列表一致，这些节点就不需要移动，只需移动那些位置不对的节点。
在这个例子里，旧列表和新列表的对应关系（按 key 识别）是：
- D 从位置 4 移到了位置 1（需要移动）
- A 从位置 1 移到了位置 2（需要移动）
- B 从位置 2 移到了位置 3（需要移动）
- C 从位置 3 移到了位置 4（需要移动）
但其实，如果我们把 D 直接移动到最前面，剩下的 A、B、C 的相对顺序本来就是对的（它们在新列表中是 A→B→C，旧列表中也是 A→B→C），所以这三者完全可以不动。真实需要移动的只有一个节点：D。
怎样快速找出那批“相对顺序本来就对”的节点？答案是：求解旧节点在新列表中位置的最长递增子序列。
算法的大致流程
Vue 3 的列表 Diff 会先进行首尾指针预判，快速处理掉头部和尾部相同的节点。当遇到中间一段乱序的区域时，才启用 LIS 优化。具体步骤：
- 建立位置映射
遍历新的一组节点，用一个数组 newIndexToOldIndexMap 记录每个新节点在旧列表中的位置（如果不存在则为 0）。
- 求解最长递增子序列
对这个位置数组求最长递增子序列（注意这里“递增”是指位置值呈现递增趋势，且值必须 > 0）。得到的结果是一个下标序列，这些下标对应的节点，他们的旧位置是按序递增的，说明它们在旧列表中的相对顺序与新列表中的相对顺序一致，因此不需要移动。
- 移动剩余节点
从新列表尾部往前遍历，如果当前下标不在最长递增子序列中，就说明它需要移动（或新建），执行 DOM 插入操作。这样，所有不在最长递增子序列中的节点会被移动到正确的位置，而在序列中的节点保持不动。
一个简单的实例
假设旧列表有 key：[e, a, b, c, d]，新列表是 [a, b, c, d, e]。
旧节点位置：
- e: 0, a: 1, b: 2, c: 3, d: 4
新列表的旧位置数组（按新顺序）：
- a → 1, b → 2, c → 3, d → 4, e → 0
得到 [1, 2, 3, 4, 0]。对这个数组求最长递增子序列，结果应是 [0, 1, 2, 3]（下标，即前四个），对应节点 a, b, c, d。这四位旧位置是递增的 1→2→3→4，说明新旧相对顺序一致，不需要移动。e 的旧位置 0 不在递增序列中，所以它需要移动。实际操作就是：保持 a, b, c, d 不动，把 e 插入到末尾。
为什么用最长递增子序列？
- 最小化 DOM 移动：移动一个真实 DOM 节点比销毁再创建要昂贵得多，LIS 能保证移动次数最少。
- 性能关键：在长列表中，这个优化效果显著。求解 LIS 的复杂度是 O(n log n)，虽然非零，但相比无优化情况下的 O(n²) 移动成本，它大大降低了总开销。
- 对开发者透明：你只需要给每个列表项一个稳定的
key，Vue 会在 Diff 时自动应用这个优化，无需手动干涉。
实际开发中的启示
最长递增子序列是 Vue 3 虚拟 DOM 的底层优化，但它的存在提醒我们一个实践要点：为列表提供唯一的、稳定的 key 至关重要。当 key 设计不当时（比如用 index 作为 key），LIS 的优化效果会被大幅削弱，甚至导致错误的 DOM 复用。理解这一原理，有助于写出更高效的列表渲染代码。