单调栈的特点:
1.自顶向下一次递增,也就是上小下大的栈
单调栈代码:
算法思想:将不符合单调栈性质的弹出,符合的输入
#include<iostream>
#include <stack>
#include<queue>
using namespace std;
void text01(){
int a[]={5,2,1,3,4};
stack<int> stk;
for(int i=0;i<5;i++){
//while循环,将不符合单调栈性质的元素依次弹出
while(!stk.empty()&&a[i]>=stk.top()){
stk.pop();
}
//循环后,要么时栈空,要么是input<top(),都应该入栈
// if(stk.empty()) stk.push(a[i]);
// else if(a[i]<stk.top()) stk.push(a[i]);
stk.push(a[i]);
}
}
int main() {
text01();
return 0;
}
单调栈的应用:
1.题目符合单调栈,自定向下一次递增性质的习题
2.笛卡尔树(基于单调栈、查询右链)
习题:P2947 [USACO09MAR] Look Up S(奶牛仰望对象)
法一:数组双重for循环
但是会超时,因为给的数据最大时1e5,双重循环时1e10,超时边缘时1e7,所以肯定会超时
#include<iostream>
#include<queue>
using namespace std;
const int N=1e5+10;
int a[N],n;
void text01(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
bool flag=false;
for(int j=i+1;j<=n;j++){
if(a[i]<a[j]){
flag=true;
cout<<j<<endl;
break;
}
}
if(!flag) cout<<"0"<<endl;
}
}
int main() {
text01();
return 0;
}
法二:利用单调栈
#include<iostream>
#include <stack>
#include<queue>
using namespace std;
const int N=1e5+10;
int h[N],n,a[N];
void text01(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>h[i];
}
stack<int> stk;
for(int i=n;i>=1;i--){
//while循环,将不符合单调栈性质的元素依次弹出
while(!stk.empty()&&h[i]>=h[stk.top()]){
stk.pop();
}
if(stk.empty()){
a[i]=0;
stk.push(i);
}
else{
a[i]=stk.top();
stk.push(i);
}
}
for(int i=1;i<=n;i++){
cout<<a[i]<<endl;
}
}
int main() {
text01();
return 0;
}