什么时候会用到单调栈（递增递减栈）的思想

carry12345678 发表于 2018-7-5 08:59
这个可以可以

哈哈哈哈我从不装b

carry12345678 发表于 2018-7-5 12:26
无形装b, 最为致命=哈哈哈哈我从不装b

自己打脸吧

呜呜好疼啊

mark zszszszszszszszszszs

我的感觉是 凡是array相关 是要求某一个小区间内极值 上单调栈就对了

这个问题很有意思

find next greater element, 用递增stack
example:
https://leetcode.com/problems/daily-temperatures/
https://leetcode.com/problems/remove-duplicate-letters/
https://leetcode.com/problems/largest-rectangle-in-histogram/
https://leetcode.com/problems/maximal-rectangle/


find next smaller element, 用递减stack
example
https://leetcode.com/problems/remove-k-digits/

套用网上流行的说法就是： 学到这个算法的时候惊为天人， 感觉跟eetcode上的大神又接近了一步，后来发现自己的水平跟大神差了不知道多少个单调栈。

举个栗子，比如有一天，某家店在发 free food，很多人在排队，于是你也赶过去凑热闹。但是由于来晚了，队伍已经很长了，想着不然就插个队啥的。但发现排在队伍最前面的都是一些有纹身的大佬，惹不起，只能赞美道，小猪佩奇身上纹，来世还做社会人。于是往队伍后面走，发现是一群小屁孩，直接全部撵走，然后排在了社会大佬们的后面。那么这就是一个单调递减的栈，按实力递减。由于栈元素是后进先出的，所以上面的例子正确的检查顺序应该是从队尾往前遍历，小屁孩都撵走，直到遇到大佬停止，然后排在大佬后面（假设这个队列已经事先按实力递减排好了）。
单调栈最重要的性质是下面！！！！

单调递增栈可以找到当前数字，左边第一个比它小的元素。
单调递减栈可以找到当前数字，左边第一个比它大的元素。