单调栈---基础数据结构与算法

简介

栈 (stack) 又名堆栈，是一种数据结构，向一个栈插入新元素又称作进栈、入栈或压栈，从一个栈删除元素又称作出栈或退栈。

栈是一种只允许在表尾进行插入和删除操作的线性表，也就是我们所说的后进先出，我们把栈想象成往一个有底的桶中放铁饼，你从桶中拿铁饼，只能拿到最上边的，放铁饼也只能在最上边开始放，如图

栈的实现分两种，数组模拟和链表实现，这里用数组模拟

栈的数组模拟

如果学过了链表，那就对栈的实现很容易上手，甚至只需要看一眼就能够领悟。

const int N =100010;
int stk[N],tt; //tt是栈顶的下标
 
//栈的插入操作 下标从1开始被使用
stk[++tt] = x ; 
 
//栈的弹出操作
--tt;
 
//判断栈是否为空
if(tt>0) not empty //不为空
else empty //为空
 
//取栈顶元素
stk[tt];

 这里大概了解了栈，那单调栈只不过是栈内元素呈单调性的栈，可能是单调递增，也可能是单调递减。

栈的主要应用场景：找出一个序列中每个数左/右边离它最近的比它大/小的数。

这里来一道题目，快速上手>

题目

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

输出解释：

3的左边没有比它小的数 输出-1

4的左边比它小的数是3 输出3

2的左边没有比它小的数 输出-1

7的左边比它小的数并且最近的是2 输出2

5的左边比它小的数并且最近的是2 输出2

暴力解法

我们首先想到的暴力算法是，我们要求第 i 个数左边比它小的数并且离它最近，那就是从 i-1 个数开始，向左边遍历，直到找到。

那代码应该这么写

for(int i = 0 ; i < n ; i++ )
{
    for( int j = i - 1 ; j >= 0 ; j-- )
    { 
        if( a[j] <= a[i] )
        {
            printf("%d ",a[j]);
            break;
        }
    }
    //
}

我们观察，暴力做法中可以有什么性质可以减少步骤？

如果有一个数的左边某个数 x 比它还大，那么在这题中 这个x永远都不会被考虑到

例如 a[x]  >=  a[y] 并且 x< y 那么 a[x] 就可以被删去，如图

图中存在这样逆序的点，当我们将所有逆序的点删除了，就得到了

这时，我们只需要将我们的 a[i] 依次与 stk[4]、stk[3]、stk[2] 、stk[1]进行比较（找到小于a[i]的）就可以得出答案

好，这里看代码领悟一下

单调栈解法

#include <iostream>
using namespace std;
 
const int 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--; //当栈中存在元素并且栈顶元素大于等于x时，从栈中弹出栈顶元素
        if (tt) printf("%d ", stk[tt]);//当存在栈顶元素小于x时，将此栈顶元素输出
        else printf("-1 ");  //当未在栈中查找到小于x的元素时，栈中所有元素均被弹出，此时栈为空，输出-1
        stk[++tt] = x; //将x插入到栈顶 
    }
 
    return 0;
}