LeetCode 300. Longest Increasing Subsequence (DP)
LeetCode 300. Longest Increasing Subsequence (DP)
ShenduCC
发布于 2020-06-01 16:54:20
发布于 2020-06-01 16:54:20
经典题目，最长递增子序列。
有O(n^2)效率，还有O(n*logn)效率的。 O(n^2)的效率很好理解的啦，就是大家最常见的那种DP
O(n*logn) 的方法是维护一个递增的栈，这个栈不等于最长递增子序列。但是数组的长度一定是等于最长递增子序列的长度的。 遍历原始数组，每次的操作是把当前元素和递增栈的最后一个元素作比较，如果大于直接入栈，否则就找到大于等于它的最小的元素，然后替换掉。这个思想的来源是贪心，而不是DP
O(n^2)
class Solution {
public:
int dp[5005];
int lengthOfLIS(vector<int>& nums) {
int ans=0;
for(int i=0;i<nums.size();i++)
{
dp[i]=1;
for(int j=i-1;j>=0;j--)
{
if(nums[i]>nums[j])
dp[i]=max(dp[i],dp[j]+1);
}
ans=max(ans,dp[i]);
}
return ans;
}
};O(n*logn)
class Solution {
public:
int dp[5005];
int len;
int lengthOfLIS(vector<int>& nums) {
len=0;
for(int i=0;i<nums.size();i++)
{
if(len==0||nums[i]>dp[len-1])
dp[len++]=nums[i];
else
{
int index = find(nums[i]);
dp[index]=nums[i];
}
}
return len;
}
int find(int x)
{
int l = 0;
int r = len-1;
while(l<=r)
{
int mid = (l+r)/2;
if(dp[mid]<x)
{
l = mid+1;
}
else if(dp[mid]>x)
{
r = mid-1;
}
else
return mid;
}
return l;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-05-28 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读