最长上升子序列2
题目 最长上升子序列 II
思路分析
自己给优化出来了
一开始想的是 要遍历一遍 找到所有比当前位置小的数 去一个一个尝试从那些位置转移过来的max
首先就是优化这个遍历找所有比当前位置小的数
可以想到用单调栈变形 只有所有比当前位置小的数才在栈中 那么找就只需要在里面找了
可是这样还是得一个一个尝试 从这些位置转移过来的max 能否考虑进一步优化
比如1367 此时来了一个5 我应该要把栈变成135的样子 这样就是单调递增的了 后续再来一个数 也是单调递增 所以就是需要用这个新来的5 去维护单调栈
怎么维护 好像只需要找到栈中第一个比5大的数就可以了 显然是二分的第二个模板
找到第一个比5大的数6的位置后 把6及其后面的全替换成5 即可
但这样的话 会使得栈的top不好更新
其实只把6替换成5就够了 序列变成了1 3 5 7 也是单调递增的 不影响后续操作
在所有的操作都完成后 栈的长度就是最长上升子序列的长度了
注意：单调栈优化的 LIS 算法只能给出整个序列的 LIS 长度 而不是序列中每个点的 LIS 长度 在要对每个点综合考虑时 就不管用了
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N];
int stk[N],top=0;
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++){
if (top == 0 || a[i] > stk[top])
stk[++top] = a[i];
else{
int l=1,r=top+1;
while(l<r){
int mid=l+r>>1;
if(stk[mid]>=a[i])
r=mid;
else
l=mid+1;
}
stk[l]=a[i];
}
}
cout<<top;//序列长度
return 0;
}
#incldue<bits/stdc++.h>
using namespace std;
int n;
int main()
{
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++)
cin >> arr[i];
vector<int>stk;
stk.push_back(arr[0]);
for (int i = 1; i < n; ++i) {
if (arr[i] > stk.back())
stk.push_back(arr[i]);
else
*lower_bound(stk.begin(), stk.end(), arr[i]) = arr[i];
}
cout << stk.size() << endl;
return 0;
}
💬 评论