最长递增子序列（LIS）：Vue Diff 算法中的核心算法题

大家好，今天我们来深入探讨一个在前端开发中非常关键但又常常被忽视的算法问题——最长递增子序列（Longest Increasing Subsequence, LIS）。你可能会问：“这和 Vue 的 Diff 算法有什么关系？”别急，我们一步步讲清楚。

---

一、什么是 LIS？为什么它重要？

1. 定义

最长递增子序列（LIS）是指在一个数组中找到一个子序列（不连续），使得这个子序列是严格递增的，并且长度最长。

举个例子：

arr = [10, 9, 2, 5, 3, 7, 101, 18]

其中最长递增子序列可以是 [2, 3, 7, 101] 或者 [2, 3, 7, 18]，长度都是 4。

✅ 注意：子序列不要求连续，但必须保持原顺序。

2. 为什么重要？

在 Vue 的虚拟 DOM diff 算法中，有一个经典优化策略叫做 “最长公共子序列匹配”（LCS-based matching），而 LIS 是其变种之一。
Vue 在更新列表时，会尝试找出新旧两个列表之间的最大匹配项，从而最小化 DOM 操作次数。如果能快速计算出最长递增子序列，就能高效地复用已有节点，避免不必要的重渲染。

👉 所以说，LIS 不只是一个面试题，它是现代框架性能优化的核心逻辑之一！

---

二、暴力解法：时间复杂度 O(n²)

最直观的方法是使用动态规划（DP）：

思路：

• 对于每个位置 i，我们检查前面所有 j < i 的元素。
• 如果 arr[j] < arr[i]，说明可以接上这个递增序列。
• 更新 dp[i] = max(dp[i], dp[j] + 1)

示例代码：

function lisBruteForce(arr) {
    const n = arr.length;
    if (n === 0) return 0;

    const dp = new Array(n).fill(1); // 初始化每个位置至少能构成长度为1的子序列

    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    return Math.max(...dp); // 返回最长长度
}

测试：

console.log(lisBruteForce([10, 9, 2, 5, 3, 7, 101, 18])); // 输出: 4

✅ 正确！但问题是：当数据量大时（比如几千个元素），O(n²) 的时间复杂度会严重拖慢性能。

数据规模	时间复杂度	实际耗时估算（粗略）
n=100	O(n²)=10k	几毫秒
n=1000	O(n²)=1M	几百毫秒
n=10000	O(n²)=100M	几秒甚至更久

⚠️ 这显然不适合用于大规模列表 diff！

---

三、优化方案：贪心 + 二分查找 —— O(n log n)

这是解决 LIS 的最优方法，也是 Vue Diff 中实际使用的思路！

核心思想：

维护一个数组 tails，其中 tails[i] 表示长度为 i+1 的递增子序列的最小结尾值。

为什么这样做有效？

• 我们的目标不是要找出具体的 LIS，而是要找到它的长度。
• 贪心地让每条递增链尽可能“短”，这样后面更容易扩展。
• 使用二分查找插入位置，保证效率。

步骤详解：

1. 初始化空数组 tails。
2. 遍历原数组每个元素 num：
   • 如果 num 大于 tails[tails.length - 1]，直接追加到末尾（增长当前最长链）。
   • 否则，在 tails 中二分查找第一个大于等于 num 的位置，并替换它（保持 tails 单调递增）。
3. 最终 tails.length 就是最长递增子序列的长度。

示例代码：

function lisOptimized(arr) {
    const tails = [];

    for (const num of arr) {
        let left = 0, right = tails.length;

        // 二分查找插入点
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (tails[mid] < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        // 替换或添加
        if (left === tails.length) {
            tails.push(num);
        } else {
            tails[left] = num;
        }
    }

    return tails.length;
}

测试：

console.log(lisOptimized([10, 9, 2, 5, 3, 7, 101, 18])); // 输出: 4

✅ 结果一致！而且时间复杂度从 O(n²) 降到 O(n log n)，大幅提升性能！

数据规模	时间复杂度	实际耗时估算（粗略）
n=100	O(n log n) ≈ 660	几毫秒
n=1000	≈ 3000	几毫秒
n=10000	≈ 33000	几毫秒

🎉 这才是工业级可用的算法！

---

四、进阶：如何还原 LIS 序列本身？

上面我们只得到了长度，但如果想得到真实的子序列（比如用于 diff 中标记哪些节点可以复用），怎么办？

我们可以借助另一个辅助数组 parent 来记录路径。

改造版本：

function lisWithSequence(arr) {
    const n = arr.length;
    if (n === 0) return { length: 0, sequence: [] };

    const tails = [];           // 存储每个长度对应的最小结尾值
    const indices = [];         // 记录 tails 中对应索引的位置
    const parent = new Array(n).fill(-1); // 记录每个元素前一个是谁

    for (let i = 0; i < n; i++) {
        const num = arr[i];
        let left = 0, right = tails.length;

        // 二分查找插入位置
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (tails[mid] < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        // 更新 tails 和 indices
        if (left === tails.length) {
            tails.push(num);
            indices.push(i);
        } else {
            tails[left] = num;
            indices[left] = i;
        }

        // 构建回溯路径
        if (left > 0) {
            parent[i] = indices[left - 1]; // 前一个元素的索引
        }
    }

    // 回溯构造 LIS 序列
    const sequence = [];
    let current = indices[tails.length - 1];
    while (current !== -1) {
        sequence.unshift(arr[current]);
        current = parent[current];
    }

    return {
        length: tails.length,
        sequence
    };
}

测试：

const result = lisWithSequence([10, 9, 2, 5, 3, 7, 101, 18]);
console.log(result); 
// 输出:
// {
//   length: 4,
//   sequence: [2, 3, 7, 101]
// }

💡 这就是 Vue Diff 中用来做节点复用的关键依据！知道哪几个节点可以直接保留，不用重新创建 DOM。

---

五、Vue Diff 如何利用 LIS？

Vue 的 diff 算法主要处理两种情况：

1. 同层节点比较（keyed diff）

   • 如果有 key，则按 key 匹配；
   • 若没有 key，则用索引比较（低效）；

2. 无 key 的列表 diff（即本节重点）

   • Vue 会将新旧两个列表分别提取出 key 或 index；
   • 然后对旧列表的索引数组做 LIS 分析，找到可复用的部分；
   • 剩下的节点进行插入/删除操作。

关键逻辑伪代码（简化版）：

function optimizeDiff(oldKeys, newKeys) {
    const oldIndices = oldKeys.map(k => findIndexInNew(newKeys, k)); // 获取旧 key 在新列表中的位置
    const lisResult = lisWithSequence(oldIndices); // 找最长递增子序列

    // lisResult.sequence 包含了可以复用的索引
    const keepIndices = new Set(lisResult.sequence);

    // 删除不在 LIS 中的节点
    const toRemove = oldIndices.filter((_, idx) => !keepIndices.has(idx));

    // 插入新的节点
    const toInsert = newKeys.filter(k => !oldKeys.includes(k));

    return { toRemove, toInsert };
}

📌 这样做的好处是：

• 最少 DOM 操作；
• 利用 LIS 找出最多可复用节点；
• 性能远优于暴力逐个比对。

---

六、对比总结：三种方法一览表

方法	时间复杂度	空间复杂度	是否可还原真实序列	适用场景
暴力 DP	O(n²)	O(n)	✅ 可以	小数据集、教学演示
优化 LIS（仅长度）	O(n log n)	O(n)	❌ 不可以	Vue Diff 核心算法
优化 LIS（带路径）	O(n log n)	O(n)	✅ 可以	Vue Diff + 自定义 diff 工具

🎯 推荐：生产环境使用优化版 LIS（带路径），既能保证性能又能支持精确 diff。

---

七、常见误区与注意事项

❗ 错误理解 1：LIS 必须是连续的？

❌ 不对！LIS 是子序列，允许跳过中间元素。例如 [1, 3, 2, 4] 的 LIS 是 [1, 3, 4] 或 [1, 2, 4]，不是 [1, 3]。

❗ 错误理解 2：只要找到最长即可，不需要具体路径？

❌ 不对！Vue Diff 中需要知道哪些节点可以复用，所以必须能还原 LIS 的具体元素。

❗ 错误理解 3：二分查找部分很难懂？

✅ 其实很简单：

• tails[i] 是长度为 i+1 的递增子序列的最小结尾值；
• 每次插入时，我们尽量让这个值“小一点”，以便后续能扩展；
• 二分查找确保插入位置正确，同时维持单调性。

---

八、实战建议（给开发者）

如果你正在开发类似 Vue 的框架或组件库，请记住以下几点：

1. 优先采用 O(n log n) 的 LIS 解法，尤其是涉及大量列表更新时；
2. 实现时务必保留路径信息，方便后续 diff 逻辑；
3. 测试边界情况：
   • 全部递减数组（如 [5,4,3,2,1] → LIS=1）
   • 全部递增数组（如 [1,2,3,4,5] → LIS=n）
   • 重复元素（需明确是否允许相等，通常要求严格递增）
4. 性能监控：对于超大数据列表（>10k），考虑分批处理或并行优化。

---

九、结语

今天我们从理论到实践，层层递进地讲解了最长递增子序列（LIS）的本质、优化方法及其在 Vue Diff 算法中的应用。这不是一道简单的面试题，而是现代前端框架背后的重要基石。

✅ 掌握 LIS，你就掌握了：

• 如何高效匹配 DOM 节点；
• 如何减少不必要的重渲染；
• 如何写出高性能的 diff 算法。

希望这篇文章让你不仅学会了 LIS，还能把它用到真实项目中去。下次当你看到 Vue 的列表更新变得飞快时，记得背后正是这个优雅的算法在默默工作！

如有疑问欢迎留言讨论，我们一起进步！