LeetCode Hot 100 - 最长递增子序列完全题解

题目描述

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

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。

示例 1：

text

输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4。

示例 2：

text

输入：nums = [0,1,0,3,2,3] 输出：4 解释：最长递增子序列是 [0,1,2,3] 或 [0,1,3,?] 等，长度为 4。

示例 3：

text

输入：nums = [7,7,7,7,7,7,7] 输出：1 解释：严格递增，相同元素不算递增，所以最长长度为 1。

示例 4：

text

输入：nums = [1,3,6,7,9,4,10,5,6] 输出：6

约束条件：

• 1 <= nums.length <= 2500

• -10^4 <= nums[i] <= 10^4

解题思路

核心思想：这是经典的最长递增子序列（LIS）问题，有两种主流解法：

1. 动态规划：O(n²) 时间，O(n) 空间

2. 贪心 + 二分查找：O(n log n) 时间，O(n) 空间

方法一：动态规划（基础解法）

思路

定义dp[i]表示以nums[i]结尾的最长递增子序列的长度。

状态转移方程：

text

dp[i] = max(dp[j]) + 1, 其中 0 ≤ j < i 且 nums[j] < nums[i]

如果前面没有比nums[i]小的数，则dp[i] = 1

最终答案：max(dp[0], dp[1], ..., dp[n-1])

代码实现

java

public int lengthOfLIS(int[] nums) { int n = nums.length; if (n == 0) return 0; int[] dp = new int[n]; int maxLength = 1; // 初始化：每个元素至少可以自己构成一个长度为1的子序列 Arrays.fill(dp, 1); for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } maxLength = Math.max(maxLength, dp[i]); } return maxLength; }

手动模拟

以nums = [10, 9, 2, 5, 3, 7, 101, 18]为例：

详细计算 i=7（nums[7]=18）：

• j=0: 10<18? 是 → dp[0]+1=2

• j=1: 9<18? 是 → dp[1]+1=2

• j=2: 2<18? 是 → dp[2]+1=2

• j=3: 5<18? 是 → dp[3]+1=3

• j=4: 3<18? 是 → dp[4]+1=3

• j=5: 7<18? 是 → dp[5]+1=4

• j=6: 101<18? 否 → 跳过

• max = 4，所以 dp[7] = 4

最终 dp 数组：[1, 1, 1, 2, 2, 3, 4, 4]
最大长度 = 4✅

复杂度分析

• 时间复杂度：O(n²) — 双重循环

• 空间复杂度：O(n) — dp 数组

优缺点

• ✅ 思路直观，容易理解

• ✅ 可以记录具体的子序列（稍作修改）

• ❌ 时间复杂度较高，n=2500 时勉强可过

方法二：贪心 + 二分查找（最优解）⭐

核心思想

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

贪心策略：为了让子序列尽可能长，我们要让末尾元素尽可能小，这样更有利于后面接上更大的数。

算法步骤：

1. 遍历每个数num

2. 在tails中找到第一个 ≥num的位置（二分查找）

3. 如果找到，替换该位置的值为num（因为更小的末尾更优）

4. 如果没找到（num大于所有tails中的数），则追加到末尾

5. 最终tails的长度就是 LIS 的长度

为什么贪心成立？

• tails数组是严格递增的

• 对于相同的长度，我们保留更小的末尾值，这样后面的数更容易接上

• 替换操作不会影响最终长度，但可能改变子序列的内容

代码实现

java

public int lengthOfLIS(int[] nums) { int n = nums.length; if (n == 0) return 0; int[] tails = new int[n]; int size = 0; // 当前 tails 的有效长度 for (int num : nums) { // 二分查找第一个 >= num 的位置 int left = 0, right = size; while (left < right) { int mid = left + (right - left) / 2; if (tails[mid] < num) { left = mid + 1; } else { right = mid; } } // left 是要替换的位置 tails[left] = num; // 如果 left == size，说明 num 大于所有已有值，长度增加 if (left == size) { size++; } } return size; }

使用库函数的简化版

java

public int lengthOfLIS(int[] nums) { int[] tails = new int[nums.length]; int size = 0; for (int num : nums) { int pos = Arrays.binarySearch(tails, 0, size, num); if (pos < 0) { pos = -pos - 1; // 获取插入点 } tails[pos] = num; if (pos == size) { size++; } } return size; }

手动模拟（关键！）

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

最终 size = 4✅

重要说明：tails数组不是真正的 LIS，只是长度相同。例如最后tails = [2, 3, 7, 18]，但原数组中没有[2,3,7,18]这个子序列（7 在 3 后面但 18 在 101 后面？）。它只是维护了每个长度的最小末尾值。

复杂度分析

• 时间复杂度：O(n log n) — 每个数二分查找 O(log n)

• 空间复杂度：O(n) — tails 数组

优缺点

• ✅ 时间复杂度最优 O(n log n)

• ✅ 空间复杂度 O(n)

• ❌ 无法直接得到具体的子序列（需要额外处理）

• ⭐ 面试推荐写法

方法三：线段树（进阶，了解即可）

思路

将数值离散化后，使用线段树维护以某个值结尾的 LIS 长度。

代码实现（简化版）

java

public int lengthOfLIS(int[] nums) { // 离散化 int[] sorted = nums.clone(); Arrays.sort(sorted); Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < sorted.length; i++) { map.put(sorted[i], i + 1); } int n = nums.length; int[] tree = new int[4 * n + 5]; for (int num : nums) { int idx = map.get(num); // 查询 [1, idx-1] 的最大值 int maxLen = query(tree, 1, 1, n, 1, idx - 1); // 更新 idx 位置为 maxLen + 1 update(tree, 1, 1, n, idx, maxLen + 1); } return query(tree, 1, 1, n, 1, n); }

复杂度分析

• 时间复杂度：O(n log n)

• 空间复杂度：O(n)

优缺点

• ✅ 时间复杂度 O(n log n)

• ✅ 可以处理更复杂的问题（如带权重的 LIS）

• ❌ 代码复杂，面试不常用

方法四：打印具体的 LIS（扩展）

思路

在 DP 的基础上，记录前驱节点，最后回溯。

代码实现

java

public List<Integer> lengthOfLISWithSequence(int[] nums) { int n = nums.length; int[] dp = new int[n]; int[] prev = new int[n]; // 记录前驱索引 Arrays.fill(prev, -1); Arrays.fill(dp, 1); int maxLen = 1; int maxIdx = 0; for (int i = 0; i < n; i++) { for (int 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]; maxIdx = i; } } // 回溯构建序列 List<Integer> sequence = new ArrayList<>(); while (maxIdx != -1) { sequence.add(0, nums[maxIdx]); maxIdx = prev[maxIdx]; } return sequence; }

方法对比总结

图文详解

动态规划过程可视化

text

nums: 10 9 2 5 3 7 101 18 dp: 1 1 1 2 2 3 4 4 状态转移图（箭头表示可以从前面转移过来）： 10 ← 无 9 ← 无 2 ← 无 5 ← 2 3 ← 2 7 ← 5, 3 101 ← 7, 5, 3, 2, ... 18 ← 7, 5, 3, 2, ...

贪心 + 二分过程可视化

text

tails 数组的变化（每个位置表示长度为 i+1 的 LIS 的最小末尾）： 步骤1: [10] → 长度1的最小末尾:10 步骤2: [9] → 长度1的最小末尾:9（更优） 步骤3: [2] → 长度1的最小末尾:2（更优） 步骤4: [2, 5] → 长度2的最小末尾:5 步骤5: [2, 3] → 长度2的最小末尾:3（更优） 步骤6: [2, 3, 7] → 长度3的最小末尾:7 步骤7: [2, 3, 7, 101] → 长度4的最小末尾:101 步骤8: [2, 3, 7, 18] → 长度4的最小末尾:18（更优） 最终 tails = [2, 3, 7, 18]，长度 = 4

常见问题 Q&A

Q1：为什么贪心+二分是正确的？

A：维护tails[i]表示长度为 i+1 的递增子序列的最小末尾。对于新的数x：

• 如果x大于所有末尾，说明可以扩展最长长度

• 否则，找到第一个≥ x的位置并替换，这样不会让长度变短，但让后面的数更容易接上
  这是一个经典的贪心证明问题。

Q2：贪心法能得到正确的 LIS 长度，但 tails 数组就是 LIS 吗？

A：不一定是。tails只保证长度正确，但元素可能不是原数组中的连续子序列。例如[2, 3, 7, 18]在原数组中并非递增子序列（18 在 7 前面？需要验证）。它只是每个长度的"潜力"值。

Q3：如果要求返回具体的 LIS，该怎么办？

A：使用 O(n²) 的 DP 并记录前驱，或者对贪心法做额外处理（维护每个位置的前驱信息）。

Q4：如何处理非严格递增（允许相等）？

A：将判断条件从nums[j] < nums[i]改为nums[j] <= nums[i]，二分查找时找第一个> num的位置。

Q5：n=2500 时 O(n²) 能过吗？

A：2500² = 6,250,000 ≈ 6 百万，在 Java 中约 0.1 秒，可以过。但如果是 n=10^5 就不能了。

扩展：最长递增子序列的变种

1. 最长非递减子序列

java

// 只需将 < 改为 ≤ if (nums[j] <= nums[i]) { dp[i] = Math.max(dp[i], dp[j] + 1); } // 贪心+二分：找第一个 > num 的位置 int pos = Arrays.binarySearch(tails, 0, size, num + 1);

2. 最长递增子序列的个数（LeetCode 673）

需要同时维护长度和个数，用两个 DP 数组。

3. 俄罗斯套娃信封问题（LeetCode 354）

先按宽度排序，再对高度求 LIS。

4. 最长数对链（LeetCode 646）

排序后求 LIS 或贪心。

总结

最长递增子序列是 LeetCode Hot 100 中的经典动态规划题目，也是面试高频题。

面试建议：

1. 先说 O(n²) 的 DP 解法（基础）

2. 再优化到 O(n log n) 的贪心+二分（进阶）

3. 解释贪心法的核心思想：维护每个长度的最小末尾

4. 如果问具体序列，可以说用 O(n²) 记录前驱

核心要点：

• 理解 DP 状态定义：dp[i]是以nums[i]结尾的 LIS 长度

• 理解贪心+二分的核心：tails[i]是长度为 i+1 的 LIS 的最小末尾

• 掌握二分查找的边界处理

一句话总结：

最长递增子序列可以用 O(n²) 的动态规划求解，但更优的是 O(n log n) 的贪心+二分：维护一个 tails 数组，每个新数通过二分找到合适位置替换或追加，最终 tails 的长度就是答案。

参考链接

• LeetCode 300. 最长递增子序列 题目链接

• LeetCode 300. 最长递增子序列 官方题解