题目描述
最长上升子序列 II
在I的基础上优化时间复杂度
算法
贪心
主要使用的是一个单调队列
贪心的思想是每次都希望使得队列中维护的同长度子序列的末尾值最小
夏季每日一题 3510. 最长公共子序列 里面的视频讲解证明了正确性。
时间复杂度
$$nlogn$$
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int nmax = 1e5 + 10;
int n;
long long q[nmax]; //模拟单调队列
int main()
{
cin >> n;
int tt = 0;
q[0] = -1; //
for(int i=0; i<n; i++)
{
long long tempnum;
scanf("%ld", &tempnum);
//二分模板1 l==r的时候停在tempnum的右边 所以采用二分模板2, 使得r去-1,让最后l跟r的值指向tempnum左边
int l = 0, r = tt;
while(l < r)
{
int mid = l + r + 1>> 1;
if(q[mid] >= tempnum) r = mid - 1; //这个>=要注意,如果加=的话保证在相等的时候l跟r也指在tempnum的左边
else l = mid;
}
q[l+1] = tempnum;
tt = max(tt, l+1);
}
cout << tt;
return 0;
}