个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
31
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章LeetCode 单调栈内容小结由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
所谓的单调栈 Monotone Stack，就是栈内元素都是单调递增或者单调递减的，有时候需要严格的单调递增或递减，根据题目的具体情况来看吧。关于单调栈，这个帖子讲的不错，而且举了个排队的例子来类比。那么，博主也举个生动的例子来说明吧：比如有一天，某家店在发 free food，很多人在排队，于是你也赶过去凑热闹。但是由于来晚了，队伍已经很长了，想着不然就插个队啥的。但发现排在队伍最前面的都是一些有纹身的大佬，惹不起，只能赞美道，小猪佩奇身上纹，来世还做社会人。于是往队伍后面走，发现是一群小屁孩，直接全部撵走，然后排在了社会大佬们的后面。那么这就是一个单调递减的栈，按实力递减。由于栈元素是后进先出的，所以上面的例子正确的检查顺序应该是从队尾往前遍历，小屁孩都撵走，直到遇到大佬停止，然后排在大佬后面（假设这个队列已经事先按实力递减排好了）.
明白了单调栈的加入元素的过程后，我们来看看它的性质，以及为啥要用单调栈。单调栈的一大优势就是线性的时间复杂度，所有的元素只会进栈一次，而且一旦出栈后就不会再进来了.
单调递增栈可以找到左起第一个比当前数字小的元素。比如数组 [2 1 4 6 5]，刚开始2入栈，数字1入栈的时候，发现栈顶元素2比较大，将2移出栈，此时1入栈。那么2和1都没左起比自身小的数字。然后数字4入栈的时候，栈顶元素1小于4，于是1就是4左起第一个小的数字。此时栈里有1和4，然后数字6入栈的时候，栈顶元素4小于6，于是4就是6左起第一个小的数字。此时栈里有1，4，6，然后数字5入栈的时候，栈顶元素6大于5，将6移除，此时新的栈顶元素4小于5，那么4就是5左起的第一个小的数字，最终栈内数字为 1，4，5.
单调递减栈可以找到左起第一个比当前数字大的元素。这里就不举例说明了，同样的道理，大家可以自行验证一下.
性质搞懂了后，下面来看一下应用，什么样的场景下适合使用单调栈呢？可以看下 Max Chunks To Make Sorted II 这篇帖子的解法四，但这道题并不是单调栈的最典型应用，只能说能想到用单调栈确实牛b，但一般情况下是不容易想到的。我们来看一些特别适合用单调栈来做的题目吧.
首推 Trapping Rain Water 这道题，虽然博主开始也没有注意到可以使用单调栈来做。但实际上是一道相当合适的题，来复习一下题目:
For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. 。
给了边界的高度（黑色部分），让求能装的水量（蓝色部分）。 为啥能用单调栈来做呢？我们先来考虑一下，什么情况下可以装下水呢，是不是必须两边高，中间低呢？我们对低洼的地方感兴趣，就可以使用一个单调递减栈，将递减的边界存进去，一旦发现当前的数字大于栈顶元素了，那么就有可能会有能装水的地方产生。此时我们当前的数字是右边界，我们从栈中至少需要有两个数字，才能形成一个坑槽，先取出的那个最小的数字，就是坑槽的最低点，再次取出的数字就是左边界，我们比较左右边界，取其中较小的值为装水的边界，然后此高度减去水槽最低点的高度，乘以左右边界间的距离就是装水量了。由于需要知道左右边界的位置，所以我们虽然维护的是递减栈，但是栈中数字并不是存递减的高度，而是递减的高度的坐标。这应该属于单调栈的高级应用了，可能并不是那么直接就能想出正确的解法.
再来看一道 Largest Rectangle in Histogram，这道求直方图中的最大矩阵的题，也是非常适合用单调栈来做的，来复习一下题目:
For example, Given height = [2,1,5,6,2,3], return 10. 。
我们可以看到，直方图矩形面积要最大的话，需要尽可能的使得连续的矩形多，并且最低一块的高度要高。有点像木桶原理一样，总是最低的那块板子决定桶的装水量。那么既然需要用单调栈来做，首先要考虑到底用递增栈，还是用递减栈来做。我们想啊，递增栈是维护递增的顺序，当遇到小于栈顶元素的数就开始处理，而递减栈正好相反，维护递减的顺序，当遇到大于栈顶元素的数开始处理。那么根据这道题的特点，我们需要按从高板子到低板子的顺序处理，先处理最高的板子，宽度为1，然后再处理旁边矮一些的板子，此时长度为2，因为之前的高板子可组成矮板子的矩形 ，因此我们需要一个递增栈，当遇到大的数字直接进栈，而当遇到小于栈顶元素的数字时，就要取出栈顶元素进行处理了，那取出的顺序就是从高板子到矮板子了，于是乎遇到的较小的数字只是一个触发，表示现在需要开始计算矩形面积了，为了使得最后一块板子也被处理，这里用了个小trick，在高度数组最后面加上一个0，这样原先的最后一个板子也可以被处理了。由于栈顶元素是矩形的高度，那么关键就是求出来宽度，那么跟之前那道 Trapping Rain Water 一样，单调栈中不能放高度，而是需要放坐标。由于我们先取出栈中最高的板子，那么就可以先算出长度为1的矩形面积了，然后再取下一个板子，此时根据矮板子的高度算长度为2的矩形面积，以此类推，直到数字大于栈顶元素为止，再次进栈，巧妙的一比！ 。
初步来总结一下单调栈吧，单调栈其实是一个看似原理简单，但是可以变得很难的解法。线性的时间复杂度是其最大的优势，每个数字只进栈并处理一次，而解决问题的核心就在处理这块，当前数字如果破坏了单调性，就会触发处理栈顶元素的操作，而触发数字有时候是解决问题的一部分，比如在 Trapping Rain Water 中作为右边界。有时候仅仅触发作用，比如在 Largest Rectangle in Histogram 中是为了开始处理栈顶元素，如果仅作为触发，可能还需要在数组末尾增加了一个专门用于触发的数字。另外需要注意的是，虽然是递增或递减栈，但里面实际存的数字并不一定是递增或递减的，因为我们可以存坐标，而这些坐标带入数组中才会得到递增或递减的数。所以对于玩数组的题，如果相互之间关联很大，那么就可以考虑考虑单调栈能否解题.
到此这篇关于LeetCode 单调栈内容小结的文章就介绍到这了,更多相关LeetCode 单调栈内容请搜索我以前的文章或继续浏览下面的相关文章希望大家以后多多支持我！ 。
原文链接：https://www.cnblogs.com/grandyang/p/8887985.html 。
最后此篇关于LeetCode 单调栈内容小结的文章就讲到这里了,如果你想了解更多关于LeetCode 单调栈内容小结的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
31
4
0
栈一种常见的特殊线性数据结构，其特殊之处在于其操作顺序，下面会详细介绍，也正因为其特性，因此栈可以轻松解决表达式求值、括号匹配、递归算法、回溯算法等等问题。 01、定义 栈的特殊性表现为操作受
目录 实践1 —— 从字符串中移除星号 栈和数组存储数据的方式一样，它们都只是元素的列表。不同之处在于栈的以下3个限制： 数据只能从栈末插入； 数据只
准备工作 工具：idea+jdk8 技术要求：java基础语法 编码环节 首先，我们得先确定下来，用什么数据来模拟栈的操作。由于是一个一个的元素放入栈里面，我们可以考虑用数组来实现。
0. 学习目标 栈和队列是在程序设计中常见的数据类型，从数据结构的角度来讲，栈和队列也是线性表，是操作受限的线性表，它们的基本操作是线性表操作的子集，但从数据类型的角度来讲，它们与线性表又有着巨大的不
在可以使用递归(在堆栈中存储状态)和对象创建(在堆中创建新对象)的场景中。 问题 在对象创建和递归之间进行选择时应考虑哪些参数？ 我的研究得出以下结论(需要验证这一点) 当可用内存较少时:使用递归 可
下面是我编写的用于检查内存对齐的示例程序。 Pavan@Pavan-pc:~/working_dir/pavan/C$ cat mem3.c #include #include
Instapaper 和 Twitterrific 等应用启动的 View 不是其导航堆栈的 Root View 。我们知道这一点，因为初始 View 已经有一个后退按钮。 Instapaper 推出
有没有办法在调试或正常运行期间的某个时刻可视化 Activity 堆栈？ 最佳答案 您可以通过 Activity 管理器获取一些有用的信息。 ActivityManager manag
我想编写一个应用层协议(protocol)，在发送 GET 请求时使用 TCP 返回特定的 ASCII 文本。我读了第一HTTP specification和 the SMTP specificati
1、堆和栈的速度性能分析 堆和栈是jvm内存模型中的2个重要组成部分，自己很早以前也总结过堆和栈的区别，基本都是从存储内
一： 概念 栈，同样是一种特殊的线性表，是一种last in first out（lifo)的形式，现实中有很多这样的例子，
java中stack类继承于vector,其特性为后进先出(lastinfirstout). 入栈和出栈实例图: 实例图的java代码实例: ?
1、单链表 1、在我们数据结构中，单链表非常重要。它里面的数据元素是以结点为单位，每个结点是由数据元素的数据和下一个结点的地址组成，在java集合框架里面 LinkedList、Ha
本文实例讲述了Python编程实现双链表，栈，队列及二叉树的方法。分享给大家供大家参考，具体如下： 1.双链表 ?
我一遍又一遍地阅读定义，但我仍然不明白ARM中的SP和LR是什么？我了解PC(它显示下一条指令的地址)，SP和LR可能类似，但我只是不明白它是什么。你能帮我一下吗？ 编辑:如果你能用例子来解释它，那就
我必须使用索引 0 作为堆栈的顶部，并且在实现此操作时遇到问题。我得到了所有 null，但输出 100、200 和 300 是我得到的唯一数字。我忽略的实现有什么问题吗？ push 方法应该实现 Ar
我正在用 Java 解决汉诺塔问题。我选择使用 Stacks 作为钉子，除了 move 方法之外，一切都正常。我有规范和 JUnit 测试类，目前通过了 7 项测试中的 6 项，但在移动测试中失败了。
这个问题在这里已经有了答案: 关闭 11 年前。 Possible Duplicate: Does this type of memory get allocated on the heap or
首先，抱歉我的英语不好。我将尝试解释我的问题: 我有一个 RootViewController(基于导航的项目)。因此，它显示了表格 View ，当用户选择表格的一行 (didSelectRowAtI
我有一个看起来像这样的类 class A { int b; void B() { int c; } } int main() { A asdf;
我是一名优秀的程序员,十分优秀！