算法模板：数据结构之单调栈

算法模板：数据结构之单调栈

定义

单调栈就是栈内元素满足单调性的栈结构。

此处的单调性分为单调递增与单调递减。

使用单调栈 可以 在线性的时间复杂度里 找出 一组数中任意一个 离它最近且比他小（大）的数。

单调栈

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

输入样例：

5
3 4 2 7 5

输出样例：

-1 3 -1 2 2

题解部分：

题目是求 数组的每个元素左边第一个比它小的数

我们用单调栈来解决

在栈顶不为空的情况下判断栈顶是否大于等于 要入栈的元素

如果 栈顶大于或等于入栈 元素 那栈顶元素 肯定不会符合要求

因为 要插入的数 比 此时的栈顶 小 ，而且更靠后 更符合“左边第一个比它小的数”

所以此时要去掉栈顶元素

知道循环到 t-- 满足 栈顶元素小于 要插入元素时

此时 栈顶 即为 要查入元素左边的第一个比它小的数

最后 把要插入的元素入栈

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int stk[N],tt;
int main()
{
    int n,x;
    cin>>n;
    while (n --){
    cin>>x;
    while(tt&&stk[tt]>=x)tt--;
    if(tt)
    cout<<stk[tt]<<" ";
    else
    cout<<"-1 ";
    stk[++tt]=x;
    }
    return 0;
}

完结散花

ok以上就是对 数据结构之单调栈 的全部讲解啦，很感谢你能看到这儿。如果有遗漏、错误或者有更加通俗易懂的讲解,欢迎小伙伴私信我，我后期再补充完善。