单调栈

视频讲解及更多习题见：【算法精讲系列】基础数据结构：单调栈 (opens new window)

一、算法思想

单调栈，就是所有元素始终保持一定的单调性的栈。

常见模型为：找出每个数左边离它最近的比它大 / 小的数。

二、算法模板

C++

int stk[N], tt = 0;

for (int i = 0; i < n; i++) {
    // 弹出栈顶不满足单调性的元素
    while (tt && check(stk[tt], i)) tt--;

    // 输出 ...
    
    // 加入当前元素
    stk[++tt] = i;
}

stack<int> stk;

for (int i = 0; i < n; i++) {
    // 弹出栈顶不满足单调性的元素
    while (!stk.empty() && check(i, stk.top())) {
        stk.pop();
    }
    
    // 输出 ...
    
    // 加入当前元素
    stk.push(i);
}

三、代码实战

AcWing 0830

---

题目：单调栈

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

输入格式

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

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

输出格式

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

数据范围

$1 \le N \le 10^5$

$1 \le \text{数列中元素} \le 10^9$

输入样例：

5

3 4 2 7 5

输出样例：

-1 3 -1 2 2

解答代码：

#include <iostream>

using namespace std;

const int N = 100010;

int stk[N], tt = 0;

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;
}