1351: 小鱼比可爱Ⅱ

使用单调栈

#include <bits/stdc++.h>
using namespace std;
const int N=1000000+10;
int a[N];
int ans[N];
stack<int> s;
int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=n;i++){while(!s.empty()&&a[s.top()]<a[i]){ans[s.top()]=i;s.pop();}s.push(i);}for(int i=1;i<=n;i++){printf("%d ",ans[i]);}
}