题解

# 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

```
5
1 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;
}