跳到主要内容

最长递增子序列

问题​

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

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

示例：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]（或 [2,5,7,101] 等）

来源：LeetCode 300. 最长递增子序列

答案​

方法一：动态规划（O(n2)O(n^2)，容易理解）​

状态定义：dp[i] = 以 nums[i] 结尾的最长递增子序列长度。

转移方程：

dp[i]=max⁡0≤j<i,nums[j]<nums[i](dp[j]+1)dp[i] = \max_{0 \leq j < i, nums[j] < nums[i]}(dp[j] + 1)
lengthOfLIS.ts
function lengthOfLIS(nums: number[]): number {
  const n = nums.length;
  const dp = new Array(n).fill(1); // 每个元素自身是长度为 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);
      }
    }
  }

  return Math.max(...dp);
}

图解：

nums: [10, 9, 2, 5, 3, 7, 101, 18]
dp:   [ 1, 1, 1, 2, 2, 3,  4,  4]

i=3(5): j=2(2<5) → dp[3]=dp[2]+1=2
i=4(3): j=2(2<3) → dp[4]=dp[2]+1=2
i=5(7): j=2(2<7) → 2, j=3(5<7) → 3, j=4(3<7) → 3 → dp[5]=3
i=6(101): 最优 dp[5]+1=4
i=7(18): j=5(7<18) → dp[5]+1=4
复杂度分析
  • 时间复杂度：O(n2)O(n^2) — 两层循环
  • 空间复杂度：O(n)O(n) — dp 数组

方法二：贪心 + 二分查找（O(nlog⁡n)O(n \log n)，最优）​

核心思路：维护一个 tails 数组，tails[i] 表示所有长度为 i+1 的递增子序列中，末尾元素的最小值。

  • 如果 nums[i] > tails 最后一个元素 → 直接追加
  • 否则 → 用二分查找找到第一个 ≥ nums[i] 的位置，替换它
lengthOfLISBinary.ts
function lengthOfLIS(nums: number[]): number {
  const tails: number[] = [];

  for (const num of nums) {
    // 二分查找：找到 tails 中第一个 >= num 的位置
    let left = 0;
    let 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; // 替换，让 tails 尽可能小
    }
  }

  return tails.length;
}

图解过程：

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

num=10:  tails=[]          → 追加  tails=[10]
num=9:   9<10, pos=0       → 替换  tails=[9]
num=2:   2<9, pos=0        → 替换  tails=[2]
num=5:   5>2               → 追加  tails=[2,5]
num=3:   3>2, 3<5, pos=1   → 替换  tails=[2,3]
num=7:   7>3               → 追加  tails=[2,3,7]
num=101: 101>7             → 追加  tails=[2,3,7,101]
num=18:  18>7, 18<101,pos=3→ 替换  tails=[2,3,7,18]

tails.length = 4 → 答案是 4
重要提醒

tails 数组的内容不是最长递增子序列本身！它只是帮助我们计算长度。 例如上面最终 tails = [2,3,7,18]，但实际的 LIS 可以是 [2,3,7,101]。

复杂度分析
  • 时间复杂度：O(nlog⁡n)O(n \log n) — 遍历 O(n)O(n)，二分 O(log⁡n)O(\log n)
  • 空间复杂度：O(n)O(n) — tails 数组

两种方法对比​

方法时间空间面试场景
DPO(n2)O(n^2)O(n)O(n)基础版，快速写出
贪心+二分O(nlog⁡n)O(n \log n)O(n)O(n)进阶优化，面试加分

常见面试追问​

Q1: 如何输出具体的最长递增子序列？​

答案：DP 方法中记录前驱节点，回溯得到路径：

function lengthOfLISWithPath(nums: number[]): number[] {
  const n = nums.length;
  const dp = new Array(n).fill(1);
  const prev = new Array(n).fill(-1); // 记录前驱

  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;
      }
    }
  }

  // 找到 dp 最大值的位置
  let maxIdx = 0;
  for (let i = 1; i < n; i++) {
    if (dp[i] > dp[maxIdx]) maxIdx = i;
  }

  // 回溯路径
  const path: number[] = [];
  let idx: number = maxIdx;
  while (idx !== -1) {
    path.unshift(nums[idx]);
    idx = prev[idx];
  }

  return path;
}

Q2: 如果求的是非严格递增子序列？​

答案：只需把条件 nums[j] < nums[i] 改为 nums[j] <= nums[i]。二分查找中改为找第一个 > num 的位置（用 tails[mid] <= num 判断）。

Q3: 最长递增子序列个数？(LeetCode 673)​

答案：在 DP 基础上增加一个 count 数组：

function findNumberOfLIS(nums: number[]): number {
  const n = nums.length;
  const dp = new Array(n).fill(1);
  const count = new Array(n).fill(1); // count[i] = 以 i 结尾的 LIS 个数

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        if (dp[j] + 1 > dp[i]) {
          dp[i] = dp[j] + 1;
          count[i] = count[j];
        } else if (dp[j] + 1 === dp[i]) {
          count[i] += count[j];
        }
      }
    }
  }

  const maxLen = Math.max(...dp);
  let total = 0;
  for (let i = 0; i < n; i++) {
    if (dp[i] === maxLen) total += count[i];
  }
  return total;
}

相关链接​