300 最长递增子序列
动态规划
思路:
- 题目求最长递增子序列,假设我们已经找了k个元素形成了子序列a,我们发现,如果想要继续增加新元素,需要关注子序列a最后一个元素
nums[i],比较nums[j]与nums[i]的关系(j > i)。这一步骤本质上关注的是子序列的末尾元素,对于子序列其他元素不关心。因此我们围绕末尾元素建模。
- 我们将
dp[i]设置为第i个元素结尾的最长递增子序列长度,确认dp[i]含义后很容易得到递推公式
-
递推公式:
遍历
nums[i]之前的元素nums[j],比较两者关系,如果nums[i] > nums[j],dp[i] = dp[j] + 1
- 遍历顺序:从左到右或从右到左都可以,只需要将索引[0, i - 1]的元素遍历一遍,默认从左到右
- 初始化:每个元素结尾的最长递增子序列长度至少为1,即该元素本身,所以\(dp[i] = 1, i \in [0, n - 1]\)
- 结果:取\(res = max(dp[i]), i \in [0, n - 1]\)
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
// dp[i]表示以nums[i]结尾的最长严格递增子序列的长度
// 默认为1,仅包含nums[i]
vector<int> dp(n, 1);
// 取dp[i]最大值为结果
int res = 1;
for(int i = 0; i < n; i++){
// 遍历j从0到i - 1
for(int j = 0; j < i; j++){
if(nums[i] > nums[j])
dp[i] = max(dp[i], dp[j] + 1);
}
res = max(res, dp[i]);
}
return res;
}
};
时间复杂度:\(O(n^2 )\),其中 n 为数组 nums 的长度。动态规划的状态数为 n,计算状态 dp[i] 时,需要 O(n) 的时间遍历 dp[0…i−1] 的所有状态,所以总时间复杂度为 \(O(n^2)\)。
空间复杂度:\(O(n)\),需要额外使用长度为 n 的 dp 数组
贪心 + 二分查找
这个优化方法很容易想到,我们想要得到尽可能长的递增序列,就需要选择和当前末尾元素nums[i]尽可能大小相近的元素,从而减小序列上升速度
选择和当前末尾元素nums[i]尽可能大小相近的元素
- 这就是贪心的思路,我们寻找比nums[i]大的元素集合,再从中找到最小的元素即可
d[i] 表示长度为i的递增序列末尾元素的最小值
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if(n == 0)
return 0;
vector<int> d(n + 1, 0);
int len = 1;
d[len] = nums[0];
for(int i = 1; i < n; i++){
if(nums[i] > d[len]){
d[++len] = nums[i];
}
else{
// 通过二分查找 找到第一个大于等于nums[i]的元素
// 注意这里是二分查找的区间为[d.begin() + 1, d.begin() + len + 1]
auto it = lower_bound(d.begin() + 1, d.begin() + len + 1, nums[i]);
// pos为第一个大于等于nums[i]的元素的索引
int pos = distance(d.begin(),it);
// 更新d[pos]为nums[i]
d[pos] = nums[i];
}
}
return len;
}
};