类似于滑动窗口,但比滑动窗口要简单。在本题中因为是向坐看(其实是向高下标的方向看)。所以从后向前去遍历,如果栈为空那么直接加入即可,如果当前的数比栈顶的数要大,那么栈顶里面的数不可能成为那个被仰望的了,所以弹出,又因为可能不止一个,所以用循环。如果比栈顶数要小证明还有可能称为那个背仰望的,接着加入栈中就可以了。
#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; }