单调栈

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

输入格式

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

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

输出格式

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

数据范围

1≤N≤1e5
1≤数列中元素≤10e9

输入样例：

1
2
5
3 4 2 7 5

输出样例：

1
-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
#include<bits/stdc++.h>
using namespace std;
int main() {
	stack<int> st;
	int n;cin>>n;
	while(n--){
		int n;cin>>n;
		while(!st.empty() && st.top() >= n){
			st.pop();
		}
		if (st.empty()) printf("%d ",-1);
		else printf("%d ",st.top());
		st.push(n);
	}
}
/*
	5
	3 4 2 7 5
	思想：单调栈即为维护栈的单调性，对于右侧的数据来说看左侧只需要一个递增的数列，如果自己比头大那选头集合自己加入并且维护整个栈，反之一直找到有意义的点

*/

板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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;
}