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

• 前言
• • 定义
  • 单调栈
• 完结散花
• 参考文献

前言

⭐️感谢相遇，唤我沈七就好。
⭐️如果能和你一起进步那就太好啦。

定义

单调栈就是栈内元素满足单调性的栈结构。
此处的单调性分为单调递增与单调递减。
使用单调栈 可以 在线性的时间复杂度里 找出 一组数中任意一个 离它最近且比他小（大）的数。

单调栈

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

输入样例：

53 4 2 7 5

输出样例：

-1 3 -1 2 2

题解部分：

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

我们用单调栈来解决

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

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

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

所以此时要去掉栈顶元素

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

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

最后 把要插入的元素入栈

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

参考文献

https://www.acwing.com/activity/content/19/

Python学习手册