字数

1888 字

阅读时间

9 分钟

最长递增子序列

思路：

1. 沿用动态规划的 `dp` 数组（`dp[i]` 表示以 `nums[i]` 结尾的 LIS 长度）。
2. 新增 `prev` 数组，`prev[i]` 记录 `nums[i]` 在 LIS 中的前一个元素索引（用于回溯子序列）。
3. 找到 `dp` 数组中的最大值及其索引后，通过 `prev` 数组反向追溯，还原出最长递增子序列。
function findLIS(nums) {
  if (nums.length === 0) return [];

  const n = nums.length;
  const dp = new Array(n).fill(1); // dp[i]：以nums[i]结尾的LIS长度
  const prev = new Array(n).fill(-1); // prev[i]：记录前一个元素的索引
  let maxLen = 1;
  let maxIndex = 0; // 最长子序列的结尾索引

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
        dp[i] = dp[j] + 1;
        prev[i] = j; // 记录前一个元素的位置
      }
    }
    // 更新最长长度和对应的结尾索引
    if (dp[i] > maxLen) {
      maxLen = dp[i];
      maxIndex = i;
    }
  }

  // 回溯构建最长子序列
  const lis = [];
  while (maxIndex !== -1) {
    lis.unshift(nums[maxIndex]); // 从后往前插入
    maxIndex = prev[maxIndex];
  }

  return lis;
}

// 示例
console.log(findLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 输出：[2, 3, 7, 101] 或 [2, 5, 7, 18]（取决于回溯路径）

#### 思路：

1. 沿用贪心算法的 `tails` 数组（存储长度为 `i+1` 的 LIS 末尾元素最小值）。
2. 新增 `indices` 数组记录 `tails` 中每个元素在原数组 `nums` 中的索引，`prev` 数组记录每个元素在 LIS 中的前一个元素索引。
3. 遍历过程中，通过二分查找确定元素位置，并同步更新 `indices` 和 `prev`。
4. 最后根据 `indices` 和 `prev` 回溯出具体子序列。
   
function findLIS(nums) {
  if (nums.length === 0) return [];

  const n = nums.length;
  const tails = []; // 存储长度为i+1的LIS的末尾元素最小值
  const indices = []; // 存储tails中元素在nums中的索引
  const prev = new Array(n).fill(-1); // 记录每个元素的前一个元素索引

  for (let i = 0; i < n; i++) {
    const num = nums[i];
    // 二分查找tails中第一个 >= num的位置
    let left = 0, right = tails.length;
    while (left < right) {
      const mid = (left + right) >> 1;
      if (tails[mid] < num) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }

    // 记录前一个元素的索引（若left>0，则前一个元素是tails[left-1]对应的索引）
    if (left > 0) {
      prev[i] = indices[left - 1];
    }

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

  // 回溯构建最长子序列
  const lis = [];
  let currentIndex = indices[indices.length - 1]; // 最长子序列的最后一个元素索引
  while (currentIndex !== -1) {
    lis.unshift(nums[currentIndex]);
    currentIndex = prev[currentIndex];
  }

  return lis;
}

// 示例
console.log(findLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 输出：[2, 3, 7, 101] 或 [2, 5, 7, 18]

为了更直观理解 Vue 2 和 Vue 3 的 diff 算法差异，我们通过可视化流程图和实例对比来描述执行流程（以同级子节点更新为例）。

场景假设

假设有一组子节点需要更新，新旧节点列表如下（key 代表节点唯一标识）：

• 旧节点：[A, B, C, D, E]（key: 1,2,3,4,5）
• 新节点：[A, C, D, F, E]（key: 1,3,4,6,5）

一、Vue 2 的 diff 算法流程（双指针遍历）

核心逻辑：双指针从两端向中间收缩，优先对比首尾节点，未命中则全量查找。

步骤可视化：

初始状态：  
旧节点：[A(1), B(2), C(3), D(4), E(5)]  → 指针：startIdx=0，endIdx=4  
新节点：[A(1), C(3), D(4), F(6), E(5)]  → 指针：startIdx=0，endIdx=4  

1. 对比旧头（A）和新头（A）：key 相同，复用节点，双指针右移  
   旧：[A, B(2), C(3), D(4), E(5)]  → startIdx=1  
   新：[A, C(3), D(4), F(6), E(5)]  → startIdx=1  

2. 对比旧尾（E）和新尾（E）：key 相同，复用节点，双指针左移  
   旧：[B(2), C(3), D(4), E]  → endIdx=3  
   新：[C(3), D(4), F(6), E]  → endIdx=3  

3. 对比旧头（B）和新尾（F）：key 不同，未命中  
   对比旧尾（D）和新头（C）：key 不同，未命中  

4. 全量查找：遍历旧节点剩余部分（B, C, D），用新头（C）的 key 查找  
   找到 C（旧索引=2），复用节点，将 C 移动到新头位置，新指针右移  
   旧：[B(2), C, D(4)]  → （C 被标记移动）  
   新：[C, D(4), F(6)]  → startIdx=2  

5. 对比旧头（B）和新头（D）：key 不同，未命中  
   对比旧尾（D）和新头（D）：key 相同，复用节点，双指针左移  
   旧：[B(2), C, D]  → endIdx=2  
   新：[D, F(6)]  → startIdx=3，endIdx=2（新指针交叉，循环结束）  

6. 清理剩余节点：  
   - 新节点剩余 [F(6)]：创建 F 插入  
   - 旧节点剩余 [B(2)]：删除 B

流程图特点：

• 指针不断收缩，优先处理首尾匹配的节点
• 未命中时需遍历旧节点查找，效率较低
• 节点移动逻辑依赖指针位置调整，步骤繁琐

二、Vue 3 的 diff 算法流程（前缀/后缀 + LIS）

核心逻辑：先复用前缀/后缀相同节点，再用“最长递增子序列（LIS）”优化中间差异节点的移动。

步骤可视化：

初始状态：  
旧节点：[A(1), B(2), C(3), D(4), E(5)]  
新节点：[A(1), C(3), D(4), F(6), E(5)]  

1. 复用前缀相同节点：从头部开始对比，A 的 key 相同，直接复用，剩余节点：  
   旧剩余：[B(2), C(3), D(4), E(5)]  
   新剩余：[C(3), D(4), F(6), E(5)]  

2. 复用后缀相同节点：从尾部开始对比，E 的 key 相同，直接复用，剩余节点：  
   旧剩余：[B(2), C(3), D(4)]  
   新剩余：[C(3), D(4), F(6)]  

3. 处理中间差异（新旧剩余都不为空）：  
   a. 建立新节点 key 映射表（快速查找）：  
      keyToNewIndexMap = { 3:0, 4:1, 6:2 }（新剩余节点的索引）  
   b. 遍历旧剩余节点，标记可复用节点在新剩余中的位置，生成 source 数组：  
      - 旧 B(2)：新节点中无，标记为 -1  
      - 旧 C(3)：对应新索引 0 → source[0] = 0  
      - 旧 D(4)：对应新索引 1 → source[1] = 1  
      → source = [-1, 0, 1]  
   c. 计算 source 中有效索引（非 -1）的最长递增子序列（LIS）：  
      有效索引为 [0, 1]，LIS 为 [0, 1]（长度 2）  
   d. 基于 LIS 移动节点：  
      - LIS 对应的节点（C、D）无需移动（已在正确顺序）  
      - 新节点剩余的 F(6) 是新增节点，插入到 D 之后  

4. 清理剩余节点：  
   - 旧节点中未复用的 B(2)：删除

流程图特点：

• 前缀/后缀快速复用，减少对比次数
• 哈希表映射替代全量查找，效率提升
• LIS 确定“无需移动的节点序列”，仅插入新增节点，移动次数最少

三、直观对比总结

阶段	Vue 2 流程	Vue 3 流程
初始对比	双指针从两端向中间遍历	先对比前缀，再对比后缀
查找复用节点	遍历旧节点（O(n)）	哈希表映射（O(1)）
节点移动逻辑	依赖指针调整，移动次数多	基于 LIS 确定不动节点，仅插入新增节点
最终操作	需多次移动+删除+创建	极少移动，主要是删除无用节点+创建新增节点

通过可视化可以看出，Vue 3 的 diff 算法通过减少对比范围、加速查找、优化移动逻辑，显著提升了性能，尤其在长列表场景下优势明显。

贡献者

jiechen

页面历史

最后编辑于 18 天前

查看完整历史

c3a58a7-feat: 增加前端发展历程