Monotone Stack Summary - 单调栈

https://blog.csdn.net/liujian20150808/article/details/50752861
你提到了两个题, 分别是 316 Remove Duplicate Letters, 402 Remove K Digits

其实不止, 你会用到单调栈的还包括有 84 Largest Rectangle in Histogram | 85 (84变形), 42 Trapping Rain Water, 739. Daily Temperatures 321. Create Maximum Number.

在我看来, 这些题里面多多少少都用到了 155 min stack | max stack 这种形式, 只不过具体计算方法略有差别.

基本上对于每个点 [j], 题里的目的都是在找 j 左边或者右边比 n[j] 大 | 小, 但是是 [inf] 或者 [sup] 的数字. 似乎并没有一个特别标准的答案说哪个题必须用那个, 但是找比当前数字大 | 小的时候, 确实无非是 inf 或者 sup..

单调栈何时用：为任意一个元素找左边和右边第一个比自己大/小的位置，用单调栈

用递增单调栈还是递减单调栈：递减栈会剔除波谷，留下波峰；递增栈剔除波峰，留下波谷

求最值的时候，最后结果有单调性

http://www.cnblogs.com/grandyang/p/8887985.html

话说博主在写Max Chunks To Make Sorted II这篇帖子的解法四时，写到使用单调栈Monotone Stack的解法时

好，废话不多说，来说单调栈吧。所谓的单调栈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中是为了开始处理栈顶元素，如果仅作为触发，可能还需要在数组末尾增加了一个专门用于触发的数字。另外需要注意的是，虽然是递增或递减栈，但里面实际存的数字并不一定是递增或递减的，因为我们可以存坐标，而这些坐标带入数组中才会得到递增或递减的数。所以对于玩数组的题，如果相互之间关联很大，那么就可以考虑考虑单调栈能否解题。

https://zhuanlan.zhihu.com/p/26465701

最后再总结一下单调栈。单调栈这种数据结构，通常应用在一维数组上。如果遇到的问题，和前后元素之间的大小关系有关系的话，（例如第一题中我们要找比某个元素大的元素，第二个题目中，前后的bar的高低影响了最终矩形的计算），我们可以试图用单调栈来解决。在思考如何使用单调栈的时候，可以回忆一下这两题的解题套路，然后想清楚，如果使用单调栈，每个元素出栈时候的意义。最后的时间复杂度，因为每个元素都出栈入栈各一次，所以是线性时间的复杂度。

先来分享一道非常简单的，我本人在google interview中遇到的题目。（大雾，当时并没有做出来。）

题目是这样的，给一个数组，返回一个大小相同的数组。返回的数组的第i个位置的值应当是，对于原数组中的第i个元素，至少往右走多少步，才能遇到一个比自己大的元素（如果之后没有比自己大的元素，或者已经是最后一个元素，则在返回数组的对应位置放上-1）。

简单的例子：

input: 5,3,1,2,4

return: -1 3 1 1 -1

explaination: 对于第0个数字5，之后没有比它更大的数字，因此是-1，对于第1个数字3，需要走3步才能达到4（第一个比3大的元素），对于第2和第3个数字，都只需要走1步，就可以遇到比自己大的元素。对于最后一个数字4，因为之后没有更多的元素，所以是-1。

暴力做的结果就是O(n^2)的时间复杂度，例如对于一个单调递减的数组，每次都要走到数组的末尾。那么用单调栈怎么做呢？先来看代码：

vector<int> nextExceed(vector<int> &input) {
 vector<int> result (input.size(), -1);
 stack<int> monoStack;
 for(int i = 0; i < input.size(); ++i) { 
  while(!monoStack.empty() && input[monoStack.top()] < input[i]) {
   result[monoStack.top()] = i - monoStack.top();
   monoStack.pop();
  }
  monoStack.push(i);
 }
 return result;
}

我们维护这样一个单调递减的stack，stack内部存的是原数组的每个index。每当我们遇到一个比当前栈顶所对应的数（就是input[monoStack.top()]）大的数的时候，我们就遇到了一个“大数“。这个”大数“比它之前多少个数大我们不知道，但是至少比当前栈顶所对应的数大。我们弹出栈内所有对应数比这个数小的栈内元素，并更新它们在返回数组中对应位置的值。因为这个栈本身的单调性，当我们栈顶元素所对应的数比这个元素大的时候，我们可以保证，栈内所有元素都比这个元素大。对于每一个元素，当它出栈的时候，说明它遇到了自己的next greater element，我们也就要更新return数组中的对应位置的值。如果一个元素一直不曾出栈，那么说明不存在next greater element，我们也就不用更新return数组了。

这里作者在数组末尾加入了一个height 0，来强迫程序在结束前，将所有元素按照顺序弹出栈。是一个很巧妙的想法。在这个例子中，对于每一个元素都只有一次入栈和出栈的操作，因此时间复杂度只有O(n)。

https://blog.csdn.net/zuzhiang/article/details/78134247

单调栈，顾名思义，是栈内元素保持一定单调性（单调递增或单调递减）的栈。这里的单调递增或递减是指的从栈顶到栈底单调递增或递减。既然是栈，就满足后进先出的特点。与之相对应的是单调队列。

1.最基础的应用就是给定一组数，针对每个数，寻找它和它右边第一个比它大的数之间有多少个数。

2.给定一序列，寻找某一子序列，使得子序列中的最小值乘以子序列的长度最大。

3.给定一序列，寻找某一子序列，使得子序列中的最小值乘以子序列所有元素和最大。

1.POJ 3250

题意：有一群牛站成一排，每头牛都是面朝右的，每头牛可以看到他右边身高比他小的牛。给出每头牛的身高，要求每头牛能看到的牛的总数。

思路：这也就是应用1所说的求每个数和它右边第一个比它大的数之间的数的个数，分别求出后相加即可。朴素的做法是双重循环遍历，时间复杂度为O(n^2)，用单调栈为O(n)。

题解：POJ 3250题解。

https://endlesslethe.com/monotone-queue-and-stack-tutorial.html

单调队列和单调栈的相同点

单调队列和单调栈的“头部”都是最先添加的元素，“尾部”都是最后添加的元素。
递增和递减的判断依据是：从栈底（队尾）到栈顶（队首），元素大小的变化情况。所以队列和栈是相反的。
它们的操作是非常相似的。当队列长度为无穷大时，递增的单调队列和递减的单调栈，排列是一样的！
原因在于，长度为无穷大的的队列不会在“头部”有popfront操作，而在“尾部”的操作是一模一样的：数据都从“尾部”进入，并按照相同的规则进行比较。
两者维护的时间复杂度都是O(n)，因为每个元素都只操作一次。

区别

队列可以从队列头弹出元素，可以方便地根据入队的时间顺序（访问的顺序）删除元素。
这样导致了单调队列和单调栈维护的区间不同。当访问到第i个元素时，单调栈维护的区间为[0, i)，而单调队列维护的区间为(lastpop, i)
单调队列可以访问“头部”和“尾部”，而单调栈只能访问栈顶（也就是“尾部”）。这导致单调栈无法获取[0, i)的区间最大值/最小值。

综上所述，单调队列实际上是单调栈的的升级版。单调栈只支持访问尾部，而单调队列两端都可以。当然，单调栈的编程上（两个函数）比单调队列（三个函数）要简单。

单调队列和单调栈的性质

下面的总结，如果没有特别指出是单调队列/单调栈，那么就不区分队列和栈，而且从“头部”到“尾部”数据是严格递减的，请读者自行注意。

具有单调性
容器中的元素个数永远不为空。（因为当添加一个元素时，它要么直接被添加到“尾部”，要么弹出k个比它小的数后再被添加到“尾部”）
对于一个元素i，我们可以知道在它左边区间，第一个比它小的值，也就是Max(v[x]|x<i&&v[x]<v[i])
在元素添加的过程中，我们会不断弹出比它小的值，最后一个弹出的值，即为所求。如果没有元素被弹出，那就无法求出，虽然这个数一定存在。
顺便在这里多提一句，第二个比它小的数是一定不知道的，因为不确定是否被弹出
对于一个元素i，我们可以知道在它左边区间，第一个比它大的值，也就是Min(v[x]|x<i&&v[x]>v[i])
在弹出比i小的所有元素后，栈顶的元素即为所求。如果栈为空，也无法求出。
根据2和3，它们是元素插入时所获得的信息，我们可以推出当元素被弹出时能获得的信息：在右边区间，第一个比它大的值。
我们可以统计在添加元素过程中，弹出了多少个元素。

注：这里的大于和小于并不严谨，是为了表述尽量简单。请读者自己注意大于/大于等于，小于/小于等于。根据原则：容器中等于e的元素也会被弹出，进行判断即可。

单调队列和单调栈的应用

单调队列

可以查询区间最值（不能维护区间k大，因为队列中很有可能没有k个元素）
优化DP（见参考文献3）
单调队列一般是用于优化动态规划方面问题的一种特殊数据结构，且多数情况是与定长连续子区间问题相关联。

单调栈即可完成的

对于某个元素i：

左边区间第一个比它小的数，第一个比它大的数
确定这个元素是否是区间最值
右边区间第一个大于它的值
到右边区间第一个大于它的值的距离
确定以该元素为最值的最长区间