单调栈 | 阿犇

Trace

acwing830 单调栈

传送门：https://www.acwing.com/problem/content/832/

Problem

给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。

输入格式

第一行包含整数 N，表示数列长度。

第二行包含 N 个整数，表示整数数列。

输出格式

共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 −1。

数据范围

$1\leq N\leq10^5 $

$1\leq数列中元素\leq10^9$

输入样例：

1 2	5 3 4 2 7 5

输出样例：

1	-1 3 -1 2 2

思路

如果$i$在$j$的左边，$a[i]\geq a[j]$，那么$a[i]$永远不会出现在答案中；

我们维护栈时，保证不包含这样的$a[i]$，最后得到的是一个单调递增的栈。

程序

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;

// 数组模拟栈
int tt;
int stk[N];
int n;

int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        while(tt&&x<=stk[tt]) tt--;
        if(tt){
            cout<<stk[tt]<<" ";
        }
        else{
            cout<<"-1 ";
        }
        stk[++tt]=x;
    }
    return 0;
}