# P5788 【模板】单调栈## 题目背景模板题，无背景。## 题目描述给出项数为 n 的整数数列 a{1...n}。定义函数 f(i)代表该a数列中第 i 个元素之后第一个大于 a_i 的元素的**下标**，即 f(i)=\min_{i<j\leq n, a_j > a_i} {j}。若不存在，则 f(i)=0。试求出 f(1...n)。## 输入格式第一行一个正整数 n。第二行 n 个正整数 a{1...n}。## 输出格式一行 n个整数表示 f(1), f(2), ..., f(n) 的值。#1##1```51 4 2 3 5```##1```2 5 4 5 0```这道题是一道模板题，跟书上的奶牛向右看一样，具体做法是从后往前遍历，栈内存储数列的序号，最开始空栈则入栈，遍历到小于栈顶则入栈，遍历到大于等于的栈顶则弹出栈顶，空栈入栈的将0存入数组，遍历到小于栈顶则栈顶是目标，存入一个数组。最后结束，顺序遍历数组。代码如下：#include<stdio.h>long long list1[3000005];long long list2[3000005];struct my_stack{long long a[3000005];int size;}st;void push(long long n,struct my_stack *p){p->a[p->size++]=n;}void pop(struct my_stack *p){p->size--;}int top(struct my_stack *p) {return p->a[p->size-1];}int empty(struct my_stack *p) {return p->size==0 ? 1 : 0 ;}int main (){int n;scanf("%d",&n);for (int i=0;i<n;i++)  {scanf("%lld",&list1[i]);list2[i]=list1[i];}for (int i=n-1;i>=0;i--){while(1){if (empty(&st)){push(i,&st);list2[i]=0;break;}else if (list1[i]<list1[top(&st)]){list2[i]=top(&st)+1;push(i,&st);break;}else { pop(&st);}}}for (int i=0;i<n-1;i++)  printf("%lld ",list2[i]);printf("%lld",list2[n-1]);return 0;}