Preface

继上篇用数组模拟栈和队列，今天我们来谈一下单调栈。

所谓单调栈其实就是栈内元素具有单调性。我们都知道：如果一个二元一次方程具有单调性，图像上表现就是递增或递减的直线，而栈同样可以具有递增或递减的单调性。

单调栈的性质：

1. 插入元素，会把栈顶的破坏单调性的元素删除，如果有多个一并删除。
2. 使用单调栈一个一个插入元素，可以找到该元素向左遍历的第一个比它小（比它大）的元素。
3. 通常用于找到离自己最近的元素中最大（最小）的一个元素。

Simulation

我们直接来模拟一下单调增的栈：一个数组 [4,9,5,7,12] 从左到右依次入栈，保持栈单调递增：

1. 遍历到4，栈为空，直接入栈，此时栈内元素为 4 。
2. 遍历到9，9比4大，9入栈为新的栈顶元素，此时栈内元素为 4, 9 。
3. 遍历到5，5比9小，9出栈，5比4大，5入栈，此时栈内元素为 4, 5 。
4. 遍历到7，7比5大，入栈，此时栈顶元素为 4，5，7 。
5. 遍历到12，12比7大，入栈，此时栈顶元素为 4，5，7，12 。

我们可以根据这个过程来先写一下伪代码：

for (遍历这个数组) {
     // 看着图写出栈的条件，单调栈没有相同元素，大于等于都要出栈
     while (栈不为空 && 栈顶元素大于等于当前要插入的元素) {
         出栈； 
     }
     入栈；
 }
 // 这样写可以省去判断栈空的过程
复制代码

Problem

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

输入：第一行包含整数 N，表示数列长度。第二行包含 N 个整数，表示整数数列。

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

// 输入样例
 5
 3 4 2 7 5
 // 输出样例
 -1 3 -1 2 2
复制代码

Solution

分析：求左边第一个比它小的数，这不就是一个单调递增的栈嘛！当元素可以入栈的时候，栈顶元素就是左侧第一个比它小的元素：

// Created by hrh on 2021/8/27
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;   // 数据范围的要求，即100010
int stk[N], tt, n, x;   // 用数组模拟栈，tt为栈顶指针
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        while(tt && stk[tt] >= x) tt--;   // 出栈
        if (tt) cout << stk[tt] << ' ';   // 栈不为空输出栈顶元素
        else cout << -1 << ' ';     // 栈为空证明左边没有更小的元素，输出-1
        stk[++tt] = x;        // 入栈
    }
}
// 如果没看懂可以再看看刚才的伪代码
// C/C++中 if(tt)，tt>0为true
复制代码

Conclusion

代码思路来自AcWing，看完相信你应该已经大概理解了什么是单调栈以及它的具体使用场景。

做些题巩固一下吧：单调栈知识点题库 - 力扣（LeetCode） (leetcode-cn.com)

如果还是没思路，可以关注我，这两天会更新几道题的详细解法。