类似于滑动窗口,但比滑动窗口要简单。在本题中因为是向坐看(其实是向高下标的方向看)。所以从后向前去遍历,如果栈为空那么直接加入即可,如果当前的数比栈顶的数要大,那么栈顶里面的数不可能成为那个被仰望的了,所以弹出,又因为可能不止一个,所以用循环。如果比栈顶数要小证明还有可能称为那个背仰望的,接着加入栈中就可以了。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000+10;
stack<int> st;
int N;
int a[maxn];
int ans[maxn];
int main() {
cin>>N;
for (int i=1;i<=N;i++) {
cin>>a[i];
}
for (int i=N;i>=1;i--) {
while (!st.empty() && a[st.top()]<=a[i]) {
st.pop();
}
if (st.empty()) {
ans[i] = 0;
} else {
ans[i] = st.top();
}
st.push(i);
}
for (int i=1;i<=N;i++) {
cout<<ans[i]<<endl;
}
return 0;
}

京公网安备 11010502036488号