AcWing 830. 单调栈
原题链接
简单
作者:
h_h_h
,
2024-02-28 14:45:30
,
所有人可见
,
阅读 22
C++ 代码
#include<bits/stdc++.h>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 100010;
int st[N];
int p=-1;
int main(){
int n;
cin >> n;
/**
//左边第一个小于它的数 :从栈顶到栈底是个递减栈
for(int i=0;i<n;i++){
int x;
cin >> x;
while(p!=-1&&st[p]>=x)p--;
if(p==-1)cout << -1<<" ";
else cout<<st[p]<<" ";
st[++p]=x;
}
**/
// 右边第一个大于它的数,从栈顶到栈底是一个递增栈
vector<int> a,res;
for(int i=0;i<n;i++){
int t;
cin >> t;
a.push_back(t);
}
reverse(a.begin(),a.end());//翻转后即求的是左边第一个大于它的数,可以用栈的性质了
for(int i=0;i<n;i++){
while(p!=-1&&st[p]<=a[i])p--;
if(p==-1) res.push_back(-1);
else res.push_back(st[p]);
st[++p]=a[i];
}
reverse(res.begin(),res.end());
for(int i=0;i<n;i++){
cout<<res[i]<<" ";
}
return 0;
}