Knowledge_Base

主题

Teeker2026-07-24
1830
7.4m

最长递增子序列代码题 ​

好的！LeetCode 300题（最长递增子序列长度）是大厂面试最高频的动规题之一，也是Vue3 Diff算法中LIS的前置基础。

面试官让你手写这道题，考察的是从暴力递推到贪心二分的优化思维。如果只写 O(n²) 的 DP，算及格；如果能写出 O(n log n) 的贪心+二分，直接高分！

第一层：基础认知（题目解读） ​

  • 题目：给你一个整数数组 nums = [2, 3, 1, 5, 4]，找出其中严格递增的子序列的最长长度。
  • 关键点：子序列不要求连续，但必须保持原数组的相对顺序。
  • 肉眼答案：[2, 3, 5] 或 [2, 3, 4]，长度均为 3。

第二层：解法一 —— 动态规划（O(n²)）【必会保底写法】 ​

  • 核心思想（DP）：定义 dp[i] 为以 nums[i] 结尾的最长递增子序列的长度。
  • 状态转移：遍历 i 之前的所有 j，如果 nums[j] < nums[i]，则 dp[i] = max(dp[i], dp[j] + 1)。
  • 初始化：每个元素至少可以自己构成一个长度为 1 的子序列，所以 dp 数组全部填 1。

手撕代码（面试时如果时间紧，写这个最稳）：

javascript
function lengthOfLIS(nums) {
  // 1. 边界：空数组返回 0
  if (nums.length === 0) return 0;

  // 2. 初始化 dp 数组，全部为 1（每个元素自身）
  const dp = new Array(nums.length).fill(1);

  // 3. 外层循环：确定子序列的结尾位置 i
  for (let i = 1; i < nums.length; i++) {
    // 4. 内层循环：遍历 i 之前的所有元素 j
    for (let j = 0; j < i; j++) {
      // 5. 如果 nums[j] < nums[i]，说明可以把 nums[i] 接在以 nums[j] 结尾的序列后面
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  // 6. 最终答案是 dp 数组中的最大值（不一定是以最后一个元素结尾）
  return Math.max(...dp);
}

// 测试用例
console.log(lengthOfLIS([2, 3, 1, 5, 4])); // 输出 3

执行过程（脑内推演）：

  • i=0（元素2）：dp[0]=1
  • i=1（元素3）：比2大，dp[1] = dp[0]+1 = 2（子序列 [2,3]）
  • i=2（元素1）：前面没有比1小的，dp[2]=1
  • i=3（元素5）：前面比5小的有2,3,1。最大 dp 是 dp[1]=2，所以 dp[3]=3（子序列 [2,3,5]）
  • i=4（元素4）：前面比4小的有2,3,1。最大 dp 是 dp[1]=2，所以 dp[4]=3（子序列 [2,3,4]）
  • 最大值为 3。

第三层：解法二 —— 贪心 + 二分查找（O(n log n)）【面试加分写法】 ​

  • 核心思想（贪心 + 纸牌游戏）：维护一个数组 tails，其中 tails[i] 表示长度为 i+1 的递增子序列的“最小末尾元素值”。
  • 关键性质：tails 数组是严格递增的（可以用二分查找）。
  • 操作逻辑：
    1. 遍历每个数字 num。
    2. 在 tails 中二分查找第一个大于等于 num 的位置（左边界）。
    3. 如果找到（left < tails.length），替换该位置为 num（让该长度子序列的尾巴更小，更有潜力）。
    4. 如果没找到（left === tails.length），说明 num 比所有尾巴都大，直接追加到 tails 末尾（子序列长度 +1）。

手撕代码（强烈建议背这个，面试官眼前一亮）：

javascript
function lengthOfLIS(nums) {
  // 边界处理
  if (nums.length === 0) return 0;

  // tails 数组：tails[i] 代表长度为 i+1 的子序列的最小末尾值
  const tails = [];

  for (const num of nums) {
    // ----- 二分查找（左边界：找第一个 >= num 的位置） -----
    let left = 0;
    let right = tails.length; // 注意：right 指向末尾的下一个位置

    while (left < right) {
      const mid = left + Math.floor((right - left) / 2); // 取中位数
      if (tails[mid] < num) {
        left = mid + 1; // 当前值太小，往右找
      } else {
        right = mid; // 当前值 >= num，往左找（找第一个）
      }
    }

    // ----- 执行替换或追加 -----
    if (left === tails.length) {
      // 情况1：num 比所有尾巴都大，追加（序列变长）
      tails.push(num);
    } else {
      // 情况2：替换掉那个位置的元素（让尾巴尽可能小）
      tails[left] = num;
    }
  }

  // tails 的长度就是最长递增子序列的长度
  return tails.length;
}

// 测试
console.log(lengthOfLIS([2, 3, 1, 5, 4])); // 输出 3

逐行执行过程（结合你的数组）：

  1. num=2：tails=[]，左边界 left=0 等于 length=0，追加 → tails=[2]
  2. num=3：tails=[2]，二分找第一个>=3的位置。left=1 等于 length=1，追加 → tails=[2, 3]
  3. num=1：tails=[2,3]，二分找第一个>=1的位置。tails[0]=2 >= 1，left=0，替换 → tails=[1, 3]（关键：把长度为1的子序列尾巴从2换成1，以后更容易增长）
  4. num=5：tails=[1,3]，找第一个>=5的位置。left=2 等于 length=2，追加 → tails=[1, 3, 5]
  5. num=4：tails=[1,3,5]，找第一个>=4的位置。mid=1（值为3）小于4，往右；mid=2（值为5）>=4，left=2。替换 → tails=[1, 3, 4]
  6. 最终 tails 长度为 3。答案正确！

第四层：面试官的“变态追问”与你的回应 ​

追问 1：“贪心+二分的 tails 数组最后存的一定是最长递增子序列本身吗？”

你的回答（极其关键）：“不一定！ tails 数组的长度正确，但tails 数组的内容不一定是真实的 LIS 序列。比如 [2, 3, 1, 5, 4]，最后 tails 存的是 [1, 3, 4]，虽然它确实是 LIS 之一，但在某些情况下（如 [0, 8, 4, 12, 2]），tails 最终可能变成 [0, 2, 12]，但真实的 LIS 可能是 [0, 4, 12]。因为贪心替换只改变了末尾最小值，并不追溯具体元素。所以这个写法只求长度，不求具体序列。 如果要还原具体序列，需要像 Vue3 源码那样加 p 前驱指针数组做回溯。”

追问 2：“如果数组里有重复元素，比如 [2, 2, 3]，你的代码还能正确输出吗？”

你的回答：“能。因为题目要求是严格递增（< 而不是 <=）。在二分查找中，我用 tails[mid] < num 往右找，找的是第一个大于等于 num 的位置。所以第二个 2 会替换掉第一个 2（tails 还是 [2]），不会追加。最终 tails=[2,3]，输出 2。这正确处理了相等元素不能重复计入的情况。”

追问 3：“既然 O(n log n) 这么好，为什么不每次都用它？”

你的回答：“因为 Vue3 的 Diff 算法中，进入 LIS 计算的通常是动态节点的数量。如果列表只有几个节点（比如 < 10 个），O(n log n) 的二分查找常数较大，甚至比简单的 O(n²) 还慢。Vue3 源码中其实也有判断，当节点数量较少时，会直接用普通的双端比较或插入排序，这就是工程中的 ‘权衡（Trade-off）’ 。”

第五层：结合简历的“展示话术” ​

面试官说：“手写一下求 LIS 长度吧。”

你接过笔，先不说代码，而是先说思路（展现工程师思维）：

“面试官，这道题我先写贪心+二分的优化版本。因为在实际业务场景中，比如我在 IAMP 平台做 Canvas 图层渲染顺序优化时，就曾用这种 O(n log n) 的算法找出最不需要调整的图层索引，从而减少 DOM 重排。它的核心在于维护一个单调递增的尾巴数组，遇到新元素就通过二分查找替换掉第一个比它大的数，保证尾巴尽可能小。”

最近更新