C101【模板】单调栈 P5788 单调栈

// 单调栈 O(n)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=3000005;
int n,a[N],ans[N],q[N];

int main(){
  scanf("%d",&n);
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  
  int top=0;  //栈顶指针初值
  for(int i=1; i<=n; i++){
    while(top>0 && a[q[top]]<a[i]){
      ans[q[top]]=i; //记录答案
      top--;         //栈顶出栈
    }
    q[++top]=i;      //栈顶入栈
  }
  
  for(int i=1;i<=n;i++) printf("%d ",ans[i]);
}