最长递增子序列

更新: 7/3/2026 字数: 0 字 时长: 0 分钟

LeetCode 第 300 题 · 中等 · 动态规划 / 贪心 + 二分经典题（LIS）

题目描述

给你一个整数数组 nums，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序——它不要求连续。

子序列 vs 子串

• 子串必须连续：[2,5,3] 的子串有 [2,5]、[5,3]；
• 子序列只需保持相对顺序、可跳跃：[2,5,3] 的子序列包含 [2,3]（跳过 5）。

本题求的是子序列，所以 [10,9,2,5,3,7,101,18] 的答案是 [2,3,7,18]（或 [2,3,7,101]），长度 4。

示例：

输入	输出	说明
[10,9,2,5,3,7,101,18]	4	最长递增子序列 [2,3,7,18]
[0,1,0,3,2,3]	4	[0,1,2,3]
[7,7,7,7,7]	1	严格递增，相等不算，只能取一个
[]	0	空数组

思路拆解：从暴力到最优

第一步：暴力枚举（先解出来）

最朴素的想法——枚举所有子序列，检查每个是否严格递增，取最长。长度为 n 的数组有 个子序列，时间复杂度 ，指数级，只能用于理解问题、无法通过大数据。

点击展开暴力解法（仅供理解，不推荐）

function lengthOfLIS_bruteForce(nums) {
  let best = 0;
  const n = nums.length;
  // 枚举每个子集（用二进制位表示选/不选）
  for (let mask = 0; mask < (1 << n); mask++) {
    let prev = -Infinity, len = 0, ok = true;
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) {
        if (nums[i] > prev) { prev = nums[i]; len++; }
        else { ok = false; break; } // 不是严格递增
      }
    }
    if (ok) best = Math.max(best, len);
  }
  return best;
}

第二步：动态规划（O(n²)）

暴力法的浪费在于反复重算。换个角度定义状态：

dp[i] = 以 nums[i] 结尾的最长递增子序列长度。

转移方程：对每个 i，往前看所有 j < i，若 nums[j] < nums[i]，说明 nums[i] 可以接在以 nums[j] 结尾的子序列后面：

初值 dp[i] = 1（每个元素自身构成长度 1）。最终答案是 max(dp)——注意不是 dp[n-1]，因为 LIS 不一定以最后一个元素结尾。

核心思路（DP）

把"最长递增子序列"拆成"以每个位置结尾的最长递增子序列"这些子问题。每个 dp[i] 只依赖它前面已算好的 dp[j]，双层循环即可填表，时间 。

点击展开 O(n²) 动态规划解法

function lengthOfLIS_dp(nums) {
  const n = nums.length;
  if (n === 0) return 0;
  const dp = new Array(n).fill(1); // 每个元素自身长度为 1
  let best = 1;
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {          // 可接龙
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    best = Math.max(best, dp[i]);
  }
  return best;
}

第三步：贪心 + 二分（最优，O(n log n)）

DP 的瓶颈在内层循环——每次都要回头扫描所有 j。能不能把"找可接龙的最长子序列"这步加速？

关键观察（贪心）：要让子序列尽可能长，就要让相同长度的递增子序列，其结尾元素尽可能小——结尾越小，后面越容易接上更多元素。

于是维护一个数组 tails：

tails[k] = 所有长度为 k+1 的递增子序列中，最小的结尾元素。

可以证明 tails 单调递增。处理每个 num 时：

• 用二分查找（lower_bound）找到 tails 中第一个 ≥ num 的位置 pos；
• 若 pos == tails.length，说明 num 比所有结尾都大 → 追加，LIS 长度 +1；
• 否则用 num 覆盖 tails[pos]——长度不变，但把该长度的结尾变得更小。

最终 tails 的长度就是 LIS 长度。二分把内层 降到 ，总复杂度 。

tails 不是真正的 LIS

tails 数组的长度永远正确，但它本身不一定是一个合法的递增子序列——因为后期的覆盖可能来自靠后的元素。若要还原真正的 LIS 序列，需额外记录每个元素被放入时的位置索引再回溯。本题只问长度，无需还原。

交互式动画演示

下面用样例 [10,9,2,5,3,7,101,18] 完整演示贪心 + 二分解法。点击 下一步 / 自动播放，观察每个 num 如何通过二分决定"追加"（绿色）还是"覆盖"（黄色），以及 tails 数组长度的变化：

贪心 + 二分 · 最长递增子序列演示

样例输入：[10, 9, 2, 5, 3, 7, 101, 18]

原数组 nums

100

91

22

53

34

75

1016

187

tails 数组（长度 = 当前 LIS 长度 = 0）

（空）

tails 数组为空。tails[k] 表示长度为 k+1 的递增子序列的「最小结尾」，其长度即当前 LIS 长度。

步骤 0 / 9

观察重点

• 上排是原数组，▲ 指向当前处理的元素；已处理的元素半透明；
• 下排是 tails 数组，每格标注它代表的子序列长度 len；
• 绿色 = 追加（LIS 变长）、黄色 = 覆盖（长度不变、结尾变小）；
• 例如 101 追加后被 18 覆盖——长度仍是 4，但结尾从 101 变小到 18，体现"贪心让结尾尽量小"。

完整代码（JavaScript）

/**
 * 最长递增子序列 —— 贪心 + 二分，时间 O(n log n)，空间 O(n)
 * @param {number[]} nums
 * @return {number}
 */
function lengthOfLIS(nums) {
  const tails = []; // tails[k]: 长度为 k+1 的递增子序列的最小结尾

  for (const num of nums) {
    // 二分查找 tails 中第一个 >= num 的位置（lower_bound）
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;   // 等价于 Math.floor((lo+hi)/2)
      if (tails[mid] < num) {
        lo = mid + 1;               // mid 处仍小于 num，答案在右侧
      } else {
        hi = mid;                   // mid 处 >= num，收缩右边界
      }
    }

    if (lo === tails.length) {
      tails.push(num);              // num 最大：追加，LIS 长度 +1
    } else {
      tails[lo] = num;              // 覆盖：该长度结尾变得更小
    }
  }

  return tails.length;              // tails 长度即 LIS 长度
}

// 测试
console.log(lengthOfLIS([10,9,2,5,3,7,101,18])); // 4
console.log(lengthOfLIS([0,1,0,3,2,3]));         // 4
console.log(lengthOfLIS([7,7,7,7,7]));           // 1
console.log(lengthOfLIS([]));                    // 0

复杂度分析

解法	时间复杂度	空间复杂度	说明
暴力枚举子序列			枚举所有子集并校验，仅用于理解
动态规划			双层循环填 dp 表，思路最直观
贪心 + 二分（最优）			二分维护 tails，规模大时首选

其中 为数组长度。贪心+二分把 DP 的内层线性扫描替换为二分查找：

边界与易错点

易错点清单

1. 空数组 / 单元素：[] 返回 0，[5] 返回 1。tails 从空开始天然覆盖。
2. 严格递增 vs 非严格：本题要求严格递增，二分用 lower_bound（第一个 ≥ num），相等时执行覆盖，从而排除重复值（如 [7,7,7] 结果为 1）。若题目改为"非严格递增（允许相等）"，需改成 upper_bound（第一个 > num）。
3. DP 的答案是 max(dp) 而非 dp[n-1]：LIS 不一定以最后一个元素结尾，务必取整个 dp 数组的最大值。
4. tails 不是最终子序列：它的长度对，但内容可能不是合法 LIS，别直接把 tails 当答案序列返回。
5. 二分边界：hi 初始为 tails.length（开区间），循环条件 lo < hi，命中 tails[mid] < num 时 lo = mid + 1，否则 hi = mid，避免死循环与漏判。
6. 可用内置二分：JS 无原生 bisect，需手写；C++ 可用 lower_bound，Python 可用 bisect_left。

一句话记忆

"相同长度，结尾越小越好"——用二分在 tails 里找位置：能变长就追加，不能变长就把结尾换更小的，tails 的长度就是答案。