洛谷 P2947 [USACO09MAR]向右看齐Look Up（单调栈）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<stack>
 4 using namespace std;
 5 const int maxn=100005;
 6 int n,ans[maxn],a[maxn];
 7 stack<int> s;
 8 int main()
 9 {
10     cin>>n;
11     for(int i=1;i<=n;i++){
12         scanf("%d",&a[i]);
13         if(s.empty()){
14             s.push(i);
15         }else{
16             while(!s.empty()&&a[s.top()]<a[i]){
17                 ans[s.top()]=i;
18                 s.pop();
19             }
20             s.push(i);
21         }
22     }
23     while(!s.empty()){
24         ans[s.top()]=0;
25         s.pop();
26     }
27     for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
28     return 0;
29 }