先看 题目
先出思路:
{
①i<j&&h[i]<h[j] 这才是可以仰望的条件,当然也可以暴力枚举去做
②我们用单调栈时pop出的条件是什么呢?当然是输入的a[i]和栈顶的a[i],如果栈顶a[i]<输入的a[i],那么就不可能是最优解,直接pop掉就可以了,但注意枚举是要从n到1枚举,存在另一个数组h[i]里输出就行
②但是h[i]的值应该存哪里呢?如果pop掉后,如果栈顶还有数(非空栈),那么存下栈顶,因为栈顶的元素已经比输入的a[i]大了,满足h[i]<h[j]; 反之为空栈,那么说明已经没有小于这个a[i]的数了,那就存下零
}
代码
#include <iostream>
#include <stack>
using namespace std;
const int N=1e5+5;
int a[N],h[N];
stack<int> s;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=n;i>=1;i--){
while(!s.empty()&&a[s.top()]<=a[i]){
s.pop();
}
if(!s.empty()){
h[i]=s.top();
}
else{
h[i]=0;
}
s.push(i);
}
for(int i=1;i<=n;i++){
cout<<h[i]<<'\n';
}
}