给你一个整数数组
nums
,找到其中
最长严格递增子序列的长度。
子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1:
输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。
示例 2:
输入:nums = [0,1,0,3,2,3]
输出:4
示例 3:
输入:nums = [7,7,7,7,7,7,7]
输出:1
提示:
- 1 <=
nums.length
<= 2500 -
−
1
0
4
-10^4
−104 <=
nums[i]
<= 1 0 4 10^4 104
进阶:
你能将算法的时间复杂度降低到 O ( n l o g ( n ) ) O(n log(n)) O(nlog(n)) 吗?
题解1 DP O ( n 2 ) O(n^{2}) O(n2)
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
int maxN = INT_MIN;
/**
dp[i] : i处数值对应的最长子序列长度
**/
for(int i = 1; i < nums.size(); i++){
for(int j = 0; j < i; j++){
if(nums[i] > nums[j])
dp[i] = max(dp[i], dp[j]+1);
}
maxN = max(maxN, dp[i]);
}
return maxN == INT_MIN ? 1 : maxN;
}
};
题解2 贪心+二分搜索(ref. from Leetcode) O ( n l o g ( n ) ) O(n log(n)) O(nlog(n))
“从左到右(序列顺序),维护一个每个元素尽可能小的LIS备选集合S”
每个元素尽可能小,这样更可能在末尾加上一个新的值,构成一个更大的LIS
只增加(add)和替换(swap),因此完成遍历后S的长度一定等于LIS的长度,部分元素可能被你替换掉了,所以在整个遍历过程中,这个集合S可能并不是LIS本身,尽管如此,LIS的元素一定曾出现在S中(但可能在遍历过程中被swap覆盖掉了)文章来源:https://www.toymoban.com/news/detail-724336.html
鼓掌!!这个思想好棒
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(1 == nums.size()) return 1;
// p[i]: 长度为i的最长上升子序列的末尾元素最小值
vector<int> p(nums.size()+1, 0);
int len = 1;
p[len] = nums[0];
for(int i = 1; i < nums.size(); i++){
if(nums[i] > p[len]){
len ++;
p[len] = nums[i];
}else{
// 在i位置不用遍历得到dp值
// 长度=len+1的子序列的最小值 > nums[i],为了保持p的递增,需要修改某个位置的值
// 用二分找到最近的j, 满足p[j] < nums[i] < p[j+1]
// s.t. p[j+1] = nums[i];
// 如果找不到, 说明所有的数都比 nums[i] 大,此时要更新 d[1],所以这里将 pos 设为 0
int left = 1;
int right = len;
int pos = 0;
// 最希望的是改p[len], 所以判断条件 有 =
// 实际上是想不用遍历,用二分检查一遍 nums[i]是不是大于len+1情况里的倒数第二个最大的数吧
while(left <= right){
int mid = (left+right) >> 1;
// 找到了j
if(nums[i] > p[mid]){
pos = mid;
left = mid+1;
}
else{
right = mid-1;
}
}
p[pos + 1] = nums[i];
}
}
return len;
}
};
文章来源地址https://www.toymoban.com/news/detail-724336.html
到了这里,关于57 最长递增子序列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!