LeetCode 力扣热题100 最长递增子序列
题目解析
最长递增子序列(LIS)
题目描述:
给定一个整数数组 nums,找到其中 最长严格递增子序列 的长度。
示例:
vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
Solution sol;
int result = sol.lengthOfLIS(nums); // 返回 4
解释:最长递增子序列是 [2, 3, 7, 18],长度为 4。
代码解析
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if (nums.empty()) return 0; // 处理空输入情况
vector<int> dp(nums.size(), 1); // dp[i] 表示以 nums[i] 结尾的最长递增子序列长度
int ans = 1; // 记录 LIS 长度,最小为 1
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) { // 如果 nums[i] 能接在 nums[j] 后面
dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(ans, dp[i]); // 维护 LIS 长度
}
return ans;
}
};
详细思路
1. 使用动态规划
定义 dp[i]
• dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。
• 初始化:所有元素至少能单独构成长度 1 的递增子序列,因此 dp[i] = 1。
状态转移方程
• 如果 nums[i] > nums[j](j < i),则 nums[i] 可以接在 nums[j] 之后:
• 更新 ans:
记录所有 dp[i] 中的最大值。
详细运行步骤
输入:
vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
1. 初始化
• dp = [1, 1, 1, 1, 1, 1, 1, 1]
• ans = 1
2. 计算 dp[i]
i = 0
• 无 j 满足 j < i,跳过。
i = 1
• j = 0,nums[1] = 9 < 10,跳过。
i = 2
• j = 0, 1,nums[2] = 2 < 10, 9,跳过。
i = 3
• j = 0, 1, 2
• nums[3] = 5 > 2 → dp[3] = max(dp[3], dp[2] + 1) = 2
• dp = [1, 1, 1, 2, 1, 1, 1, 1]
• ans = 2
i = 4
• j = 0, 1, 2
• nums[4] = 3 > 2 → dp[4] = max(dp[4], dp[2] + 1) = 2
• dp = [1, 1, 1, 2, 2, 1, 1, 1]
• ans = 2
i = 5
• j = 0, 1, 2, 3, 4
• nums[5] = 7 > 2, 5, 3 → dp[5] = max(dp[5], dp[3] + 1) = 3
• dp = [1, 1, 1, 2, 2, 3, 1, 1]
• ans = 3
i = 6
• j = 0, 1, 2, 3, 4, 5
• nums[6] = 101 > 2, 5, 3, 7 → dp[6] = max(dp[6], dp[5] + 1) = 4
• dp = [1, 1, 1, 2, 2, 3, 4, 1]
• ans = 4
i = 7
• j = 0, 1, 2, 3, 4, 5, 6
• nums[7] = 18 > 2, 5, 3, 7 → dp[7] = max(dp[7], dp[5] + 1) = 4
• dp = [1, 1, 1, 2, 2, 3, 4, 4]
• ans = 4
最终 dp 状态
[1, 1, 1, 2, 2, 3, 4, 4]
最大值 4,即最长递增子序列长度为 4。
时间复杂度
• 外层循环 O(n)
• 内层循环 O(n)
• 总复杂度 O(n^2)
贪心+二分查找
题目解析
最长递增子序列(LIS)
给定一个整数数组 nums,找到其中 最长严格递增子序列 的长度。
示例:
vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
Solution sol;
int result = sol.lengthOfLIS(nums); // 返回 4
解释:最长递增子序列是 [2, 3, 7, 18],长度为 4。
代码解析
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> lis; // 维护 LIS 序列
for (int num : nums) {
auto it = lower_bound(lis.begin(), lis.end(), num);
if (it == lis.end()) {
lis.push_back(num); // 新增更长的 LIS
} else {
*it = num; // 替换以保持最优结构
}
}
return lis.size();
}
};
思路解析(贪心 + 二分查找)
1. 使用 lis 维护当前的递增子序列
我们不需要真正构造出 LIS 序列,而是用 贪心 + 二分查找 来维护一个数组 lis:
• lis[i] 表示长度为 i+1 的递增子序列的 最小 结尾元素。
• 我们遍历 nums,对每个 num,找到 lis 中 第一个大于等于 num 的位置(使用 lower_bound),然后替换或追加。
2. 状态转移
1. 如果 num 大于 lis 的最大元素:
• 直接追加 num 到 lis 末尾,增加 LIS 长度。
2. 否则:
• 用 lower_bound 找到 lis 中 第一个大于等于 num 的位置 并替换,这样可以保持 lis 的递增性质,并尽可能保持小的元素,给后续的 num 提供更好的递增空间。
3. 结果
• lis 的长度即为 LIS 长度(因为 lis 存的是递增子序列的结尾元素)。
lower_bound 解析
作用
auto it = lower_bound(lis.begin(), lis.end(), num);
• lower_bound(begin, end, value) 返回 第一个 >= value 的元素位置。
• 如果 num 小于 lis 中的某些元素,它会返回可以替换的最小元素的位置。
• 如果 num 大于 lis 里所有元素,返回 lis.end()(表示 num 需要追加到 lis)。
示例
vector<int> lis = {2, 3, 7, 18};
auto it1 = lower_bound(lis.begin(), lis.end(), 5); // 返回 7 的位置
auto it2 = lower_bound(lis.begin(), lis.end(), 7); // 返回 7 的位置
auto it3 = lower_bound(lis.begin(), lis.end(), 20); // 返回 lis.end()
详细运行步骤
输入
vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
初始状态
• lis = {}
遍历 nums
Step 1:num = 10
• lower_bound(lis, 10) → lis 为空,返回 end()。
• 10 追加到 lis:
lis = {10}
Step 2:num = 9
• lower_bound(lis, 9) → 10 位置替换:
lis = {9}
Step 3:num = 2
• lower_bound(lis, 2) → 9 位置替换:
lis = {2}
Step 4:num = 5
• lower_bound(lis, 5) → 大于 2 的第一个位置(插入 5):
lis = {2, 5}
Step 5:num = 3
• lower_bound(lis, 3) → 5 位置替换:
lis = {2, 3}
Step 6:num = 7
• lower_bound(lis, 7) → 大于 3 的第一个位置(插入 7):
lis = {2, 3, 7}
Step 7:num = 101
• lower_bound(lis, 101) → 101 追加到 lis:
lis = {2, 3, 7, 101}
Step 8:num = 18
• lower_bound(lis, 18) → 101 位置替换:
lis = {2, 3, 7, 18}
最终 lis 状态
[2, 3, 7, 18]
长度 4,即 最长递增子序列长度。
时间复杂度
• 每个 num 需要 O(log n) 进行 lower_bound 查找。
• 最多 n 次操作(遍历 nums)。
• 总复杂度 O(n log n),比 O(n²) 的 DP 版本更高效。
总结
方法 | 时间复杂度 | 适用情况 |
---|---|---|
动态规划 O(n²) | 适用于 n ≤ 1000 | |
贪心 + 二分查找 O(n log n) | 适用于 n ≤ 10^5 |
核心思想
• 用 lis 维护递增子序列。
• lower_bound(lis, num) 找到 第一个 >= num 的位置:
• 若 num 大于 lis 最大值 → 追加到 lis。
• 否则 → 替换第一个大于等于 num 的元素。
最终 lis.size() 就是 LIS 长度!🚀