数据结构 - 单调栈

栈结构实现，但是存入的数据具有某种性质的单调性。这个单调性可以是递增也可以是递减。

具体操作就是：

• 确定某种单调性
• 按照这种单调性，从栈顶往栈底依次弹出数据
• 如果不满足这种单调性就一直弹出数据，直到满足性质或者弹空栈
• 压入数据

---

题目来源: https://www.acwing.com/problem/content/832/

给定一个长度为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

C++

#include <iostream>

using namespace std;
const int N = 100010;
int n, s[N], idx, x;

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