动画：什么是单调栈？

灰太狼 2024-04-17 23:20 48阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

作者 | 程序员小吴

来源 | 五分钟学算法

### 定义 ###

小伙伴们都应该非常熟悉栈，栈的一个很鲜明的性质就是：**先进后出** 。

而所谓 **单调栈** 则是在栈的 **先进后出** 基础之上额外添加一个特性：**从栈顶到栈底的元素是严格递增（or递减）**。

具体进栈过程如下：

*  对于单调递增栈，若当前进栈元素为 `e`，从栈顶开始遍历元素，把小于 `e` 或者等于 `e` 的元素弹出栈，直接遇到一个大于 `e` 的元素或者栈为空为止，然后再把 `e` 压入栈中。
 *  对于单调递减栈，则每次弹出的是大于 `e` 或者等于 `e` 的元素。

### 例子 ###

以 **单调递增栈** 为例进行说明。

现在有一组数

3，4，2，6，4，5，2，3

让它们从左到右依次入栈。

具体过程如下：

![640?wx\_fmt=png][640_wx_fmt_png]

### 动画描述 ###

![640?][640]

**有话要说?**

**Q:** **你在 LeetCode 中遇到过哪题需要使用单调栈来解决的？**

欢迎留言与大家分享

**有热门推荐?**

1.【程序员】[全球最厉害的 14 位程序员][14]

2.【GitHub】[我在 GitHub 上看到了一个丧心病狂的开源项目！][GitHub]

3.【算法】[动画：七分钟理解什么是KMP算法][KMP]

4.【数据结构】[十大经典排序算法动画与解析，看我就够了][Link 1]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

[640_wx_fmt_jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/dd1b8bdac82d431faff3e6fe4205d447.png
[640_wx_fmt_png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/ca019e593aed4eaeb6aab0d057147405.png
[640]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/db8f4e8eb22b4c05a5a83a2781ac2a14.png
[14]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247486099&idx=1&sn=6ea84944fe6a3d6dd1af2b00f3e53002&chksm=fa0e6512cd79ec04c8e8c63e74d78cc23629b88290a8e0642e5e44601f99fc39a3ea530867bc&scene=21#wechat_redirect
[GitHub]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247486254&idx=1&sn=654c208601879fe1b76c682a069a4e6a&chksm=fa0e64afcd79edb960a9863c7af7e6de5893da2326e6eca2bcd9d68061966d200ba0e189ab91&scene=21#wechat_redirect
[KMP]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485939&idx=1&sn=b25f39b5644da92c4047bbbd9936f73c&chksm=fa0e6672cd79ef64dda0a21e23c2817edf4a64cbb75b9bed328d6519c6cd4fef36d03a4cb309&scene=21#wechat_redirect
[Link 1]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[640_wx_fmt_jpeg 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/862e69f192ac452ca423fa6833754723.png