LeetCode 单调栈内容小结

LeetCode Monotone Stack Summary 单调栈小结

所谓的单调栈 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 单调栈内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(10.正则表达式匹配)

    [LeetCode] 10. Regular Expression Matching 正则表达式匹配 Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'. '.' Matches any single character. '*' Matches zero or more of the preceding element. T

  • C++实现LeetCode(44.外卡匹配)

    [LeetCode] 44. Wildcard Matching 外卡匹配 Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'. '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequenc

  • C++实现LeetCode(42.收集雨水)

    C++实现LeetCode(42.收集雨水)

    [LeetCode] 42. Trapping Rain Water 收集雨水 Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. The above elevation map is represented by array [0,1,0,2,1,

  • C++实现LeetCode(验证数字)

    [LeetCode] Valid Number 验证数字 Validate if a given string can be interpreted as a decimal number. Some examples: "0" => true " 0.1 " => true "abc" => false "1 a" => false "2e10" => true "

  • C++实现LeetCode(131.拆分回文串)

    [LeetCode] 131.Palindrome Partitioning 拆分回文串 Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Example: Input: "aab" Output: [ ["aa","b"

  • C++实现LeetCode(11.装最多水的容器)

    C++实现LeetCode(11.装最多水的容器)

    [LeetCode] 11. Container With Most Water 装最多水的容器 Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two

  • C++实现LeetCode(验证回文字符串)

    [LeetCode] 125.Valid Palindrome 验证回文字符串 Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. For example, "A man, a plan, a canal: Panama" is a palindrome. "race a car" is not a

  • LeetCode 单调栈内容小结

    LeetCode 单调栈内容小结

    LeetCode Monotone Stack Summary 单调栈小结 所谓的单调栈 Monotone Stack,就是栈内元素都是单调递增或者单调递减的,有时候需要严格的单调递增或递减,根据题目的具体情况来看吧.关于单调栈,这个帖子讲的不错,而且举了个排队的例子来类比.那么,博主也举个生动的例子来说明吧:比如有一天,某家店在发 free food,很多人在排队,于是你也赶过去凑热闹.但是由于来晚了,队伍已经很长了,想着不然就插个队啥的.但发现排在队伍最前面的都是一些有纹身的大佬,惹不起,只

  • C++实现LeetCode(84.直方图中最大的矩形)

    C++实现LeetCode(84.直方图中最大的矩形)

    [LeetCode] 84. Largest Rectangle in Histogram 直方图中最大的矩形 Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. Above is a histogram where width of e

  • C++实现LeetCode(768.可排序的最大块数之二)

    [LeetCode] 768.Max Chunks To Make Sorted II 可排序的最大块数之二 This question is the same as "Max Chunks to Make Sorted" except the integers of the given array are not necessarily distinct, the input array could be up to length 2000, and the elements cou

  • C++实现LeetCode(33.在旋转有序数组中搜索)

    [LeetCode] 33. Search in Rotated Sorted Array 在旋转有序数组中搜索 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If f

  • C++实现LeetCode(155.最小栈)

    [LeetCode] 155. Min Stack 最小栈 Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. getM

  • SQL实现LeetCode(175.联合两表)

    [LeetCode] 175.Combine Two Tables 联合两表 Table: Person +-------------+---------+ | Column Name | Type    | +-------------+---------+ | PersonId    | int     | | FirstName   | varchar | | LastName    | varchar | +-------------+---------+ PersonId is the

  • Go中使用单调时钟获得准确的时间间隔问题

    Go中使用单调时钟获得准确的时间间隔问题

    目录 墙上时钟与单调时钟 墙上时钟 单调时钟 Time的结构 Since的实现 小结 参考资料 墙上时钟与单调时钟 墙上时钟 墙上时钟也称为墙上时间.大多是1970年1月1日(UTC)以来的秒数和毫秒数. 墙上时间可以和NTP(Network Time Protocal,网络时间协议)同步,但是如果本地时钟远远快于NTP服务器,则强制重置之后会跳到先前某个时间点.(这里不是很确定,猜测是如果时间差的不多,则调整石英晶体振荡器的频率,慢慢一致.如果差很多,则强行一致) 单调时钟 机器大多有自己的石

  • golang 墙上时钟与单调时钟的实现

    目录 墙上时钟与单调时钟 墙上时钟 单调时钟 Time的结构 Since的实现 小结 参考资料 墙上时钟与单调时钟 墙上时钟 墙上时钟也称为墙上时间.大多是1970年1月1日(UTC)以来的秒数和毫秒数. 墙上时间可以和NTP(Network Time Protocal,网络时间协议)同步,但是如果本地时钟远远快于NTP服务器,则强制重置之后会跳到先前某个时间点.(这里不是很确定,猜测是如果时间差的不多,则调整石英晶体振荡器的频率,慢慢一致.如果差很多,则强行一致) 单调时钟 机器大多有自己的石

  • window下注册服务的命令小结

    1. 描述:     SC 是用于与服务控制管理器通信的命令行程序 .    用法:  sc <server> [command] [service name] <option1> <option2>... 选项 <server> 的格式为 可以键入 "sc [command]"以获得命令的进一步帮助 命令: query---------------查询服务的状态,或枚举服务类型的状态.           queryex--------

  • Spring Boot Actuator监控端点小结

    Spring Boot Actuator监控端点小结

    在Spring Boot的众多Starter POMs中有一个特殊的模块,它不同于其他模块那样大多用于开发业务功能或是连接一些其他外部资源.它完全是一个用于暴露自身信息的模块,所以很明显,它的主要作用是用于监控与管理,它就是:spring-boot-starter-actuator. spring-boot-starter-actuator模块的实现对于实施微服务的中小团队来说,可以有效地减少监控系统在采集应用指标时的开发量.当然,它也并不是万能的,有时候我们也需要对其做一些简单的扩展来帮助我们

随机推荐