单调栈模板

模板

1
2
3
4
5
6
7
8
9
10
11

常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}



题目描述：

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

输入格式
第一行包含整数 N，表示数列长度。

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

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

数据范围

1≤N≤10^5
1≤数列中元素≤10^9

输入样例：

5
3 4 2 7 5

输出样例：

-1 3 -1 2 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;

const int N = 100010;

int stk[N] , tt;

int main(){
    int n;
    cin >> n;
    while(n--){
        int x;
        scanf("%d",&x);
        while (tt && stk[tt] >= x) tt--;
        if(!tt) printf("-1 ");
        else printf("%d ",stk[tt]);
        stk[++tt] = x;
    }
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<stdio.h>
#define N 100010

int stk[N], tt ; 

int main(){
    int n;
    scanf("%d",&n);
    
    while(n--){
        int x;
        scanf("%d",&x);
        
        while(tt && stk[tt] >= x) tt--; //如果栈顶元素大于当前待入栈元素，则出栈
        if(!tt) printf("-1 ");          //如果栈空，则没有比该元素小的值。
        else printf("%d ",stk[tt]);     //栈顶元素就是左侧第一个比它小的元素。
        stk[++tt] = x;
        
    }
    return 0;
}