动画:什么是单调栈?

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

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

动画:什么是单调栈?

作者 | 程序员小吴

来源 | 五分钟学算法


定义

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

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

具体进栈过程如下:

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

例子

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

现在有一组数

3,4,2,6,4,5,2,3

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

具体过程如下:

动画:什么是单调栈?

动画描述

动画:什么是单调栈?

有话要说👇

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

欢迎留言与大家分享

有热门推荐👇

1.程序员全球最厉害的 14 位程序员

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

3.【算法动画:七分钟理解什么是KMP算法

4.【数据结构十大经典排序算法动画与解析,看我就够了!

动画:什么是单调栈?

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 动画:什么是单调栈?

我还会在以下平台发布内容

GitHub 哔哩哔哩