企业官网建设流程全解析

LeetCode 300：最长递增子序列

1. 题目核心

给定整数数组nums，求其中最长严格递增子序列的长度。子序列不要求连续，但必须保持原数组中的相对顺序。
例如：

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

一种最长递增子序列：

2 → 3 → 7 → 101

长度为：

4

注意：

子数组：必须连续 子序列：可以跳过中间元素

2. 思路一：DFS / 枚举

对于每个数字，都可以考虑：

选择它 不选择它

然后枚举所有可能的子序列，判断是否严格递增并记录最大长度。这种方法会产生大量重复情况，最坏接近指数级复杂度，不适合作为主解。

3. 思路二：动态规划 DP

3.1 DP 状态定义

这题最关键的是不能只记录“当前最长的那一条序列”，因为当前数字可能接不上最长序列，却可以接在另一条较短但结尾更小的序列后面，并在以后反超。
因此定义：

dp[i] = 以 nums[i] 作为最后一个数字时， 最长递增子序列的长度

例如：

nums = [1,5,2,3,4]

可能得到：

nums：1 5 2 3 4 dp： 1 2 2 3 4

其中：

dp[1] = 2 → 1,5 dp[2] = 2 → 1,2

虽然两者长度相同，但是1,2的结尾更小，所以后面可以继续接：

1 → 2 → 3 → 4

最终超过原来的1 → 5。

3.2 状态转移

现在处理nums[i]，检查它前面的所有位置：

j = 0 ~ i-1

如果：

nums[j] < nums[i]

说明nums[i]可以接在以nums[j]结尾的递增子序列之后。
原来的长度：

dp[j]

加上当前数字：

dp[j] + 1

因为可能有多个j都满足条件，所以选择最大的：

dp[i] = max(dp[i], dp[j] + 1);

完整关系：

对于所有 j < i： 如果 nums[j] < nums[i] dp[i] = max(dp[i], dp[j] + 1)

3.3 为什么初始化全部为 1

任何一个数字单独拿出来，都能形成长度为1的递增子序列：

vector<int> dp(n, 1);

例如：

[7]

本身就是长度为1的递增子序列。

3.4 为什么不能只和前一个数字比较

错误思路：

if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1; else dp[i] = 1;

这算的是连续递增子数组，不是递增子序列。
例如：

nums = [0,1,0,3,2,3]

最长递增子序列：

0 → 1 → 2 → 3

长度为4。
其中2并不比它前面的3大：

3 > 2

但它可以跳过3，接在：

0 → 1

后面。

3.5 示例完整推导

nums = [0,1,0,3,2,3]

初始化：

dp = [1,1,1,1,1,1]

处理1：

0 < 1 dp[1] = dp[0] + 1 = 2 dp = [1,2,1,1,1,1]

处理第二个0：

前面没有比0小的数字 dp[2] = 1 dp = [1,2,1,1,1,1]

处理3：

0 < 3 → 1+1=2 1 < 3 → 2+1=3 0 < 3 → 1+1=2 dp[3] = 3 dp = [1,2,1,3,1,1]

处理2：

0 < 2 → 2 1 < 2 → 3 0 < 2 → 2 3 > 2 → 不能接 dp[4] = 3 dp = [1,2,1,3,3,1]

最后处理3：

2 < 3 dp[4] + 1 = 4

得到：

dp = [1,2,1,3,3,4]

答案：

4

3.6 为什么最终不能直接返回dp[n-1]

因为：

dp[i]

表示的是：

必须以nums[i]结尾的最长递增子序列。
整个数组的最长递增子序列不一定以最后一个数字结束。
例如：

nums = [1,2,3,0] dp = [1,2,3,1]

答案应该是：

3

而不是：

dp[3] = 1

所以需要：

maxLen = max(maxLen, dp[i]);

4. C++：DP 解法

class Solution { public: int lengthOfLIS(vector<int>& nums) { int n = nums.size(); // dp[i]：以 nums[i] 结尾的最长递增子序列长度 vector<int> dp(n, 1); int maxLen = 1; for (int i = 1; i < n; ++i) { for (int j = 0; j < i; ++j) { if (nums[j] < nums[i]) { dp[i] = max(dp[i], dp[j] + 1); } } maxLen = max(maxLen, dp[i]); } return maxLen; } };

复杂度：

时间复杂度：O(n²) 空间复杂度：O(n)

5. 最优思路：贪心 + 二分查找

DP 的问题是每个nums[i]都要检查前面的所有数字，所以需要O(n²)。
可以维护一个数组：

tails

其中：

tails[len-1] = 长度为 len 的递增子序列中， 能够得到的最小结尾值

例如处理：

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

过程大致为：

10 → [10] 9 → [9] 2 → [2] 5 → [2,5] 3 → [2,3] 7 → [2,3,7] 101 → [2,3,7,101] 18 → [2,3,7,18]

最终：

tails.size() = 4

所以最长递增子序列长度为4。
注意：

tails不一定是真实的最长递增子序列，它主要用来记录“同样长度下尽可能小的结尾”。

5.1 为什么结尾越小越好

例如已经有：

1 → 5

又遇到：

2

虽然：

1 → 2

长度仍然是2，但结尾从5变成2。
显然：

以2结尾

比：

以5结尾

更容易继续接3、4等数字。
所以我们始终希望：

同样长度的递增子序列，结尾越小越好。

5.2 每个数字怎么处理

对于当前数字x：

• 如果x比tails所有数字都大，说明可以延长最长递增子序列，直接放到末尾；
• 否则找到tails中第一个大于等于x的位置，用x替换它。

例如：

tails = [2,5] 当前 x = 3

找到第一个：

>= 3

的是5，替换：

[2,5] ↓ [2,3]

长度没变，但结尾变小了，为后面留下更多可能。

5.3 为什么找“第一个 >= x”

题目要求的是严格递增。
如果：

tails = [2,3,7] x = 3

不能把另一个3接到后面形成：

2 → 3 → 3

因为不是严格递增。
所以要找到第一个：

>= x

的位置进行替换。
C++ 正好可以使用：

lower_bound()

6. C++：最优解 O(n log n)

class Solution { public: int lengthOfLIS(vector<int>& nums) { vector<int> tails; for (int x : nums) { auto it = lower_bound(tails.begin(), tails.end(), x); if (it == tails.end()) { tails.push_back(x); } else { *it = x; } } return tails.size(); } };

复杂度：

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

7. Java：最优解

class Solution { public int lengthOfLIS(int[] nums) { int[] tails = new int[nums.length]; int size = 0; for (int x : nums) { int left = 0; int right = size; while (left < right) { int mid = left + (right - left) / 2; if (tails[mid] < x) { left = mid + 1; } else { right = mid; } } tails[left] = x; if (left == size) { size++; } } return size; } }

8. Java 语法解释

8.1 创建数组

int[] tails = new int[nums.length];

创建一个和nums一样长的整数数组。

8.2 增强 for 循环

for (int x : nums)

表示依次取出数组中的每个数字，对应 C++：

for (int x : nums)

8.3 二分查找范围

int left = 0; int right = size;

查找范围是：

[0, size)

寻找第一个：

tails[index] >= x

的位置。

8.4 二分判断

if (tails[mid] < x) { left = mid + 1; } else { right = mid; }

如果：

tails[mid] < x

说明当前位置太小，答案一定在右边。
否则当前mid有可能就是第一个>= x的位置，因此：

right = mid;

8.5left == size

如果二分结束：

left == size

说明整个tails中都没有>= x的数字，也就是：

x 比所有结尾都大

可以延长最长递增子序列：

size++;

9. Python：最优解

from bisect import bisect_leftclass Solution: def lengthOfLIS(self, nums): tails = [] for x in nums: index = bisect_left(tails, x) if index == len(tails): tails.append(x) else: tails[index] = x return len(tails)

10. Python 语法解释

10.1bisect_left

from bisect import bisect_left

导入 Python 自带的二分查找函数。

index = bisect_left(tails, x)

表示：

在已经有序的tails中寻找第一个>= x的位置。
基本对应 C++：

lower_bound(tails.begin(), tails.end(), x)

10.2 空列表

tails = []

创建一个空列表。

10.3append

tails.append(x)

把x添加到列表末尾，对应 C++：

tails.push_back(x);

10.4len

len(tails)

表示列表长度。

11. 两种主要解法对比

12. 核心记忆

12.1 DP 定义

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

12.2 DP 转移

对于所有：

j < i

如果：

nums[j] < nums[i]

则：

dp[i] = max(dp[i], dp[j] + 1);

本质是：

当前数字去前面寻找所有比自己小的数字，从它们对应的递增子序列中选择最长的一条，再把自己接上去。

12.3 为什么不能只保存一条最长序列

例如：

1 → 5 1 → 2

虽然长度都是2，但第二条结尾更小，未来更容易继续：

1 → 2 → 3 → 4

所以 DP 要给每个位置分别保存一个状态，不能只记录一个全局最长序列。

12.4 最优解核心

维护：

tails[len-1] = 长度为 len 的递增子序列中 最小的结尾值

当前数字x：

比所有结尾都大 → 添加到 tails 末尾 否则 → 找第一个 >= x 的位置并替换

最后：

tails 的长度 = LIS 长度

一句话记忆：

DP 是“当前数字去前面找所有能接的序列”；二分优化则是“只保留每种长度下最小的结尾”，因为结尾越小，未来越容易继续增长。