单调栈-算法总结
单调栈，顾名思义，是一种单调的栈，单调递增或单调递减，在栈内的元素根据在栈中的位置单调。概念本身不复杂，主要是要明白其适用于什么样的场景，常用于解决什么问题。
场景一： 下一个最大/最小值
看到一个很有趣的评论：“他向远方望去，无法看到高山背后的矮山，只看到一座座更高的山峰。“，很生动形象的展示了这个场景
经典模版题，下一个最高值出现在什么时候，一般是对一个数组进行循环：
从栈中peek元素，如果低于该值，就push，如果高于该值，就循环pop，直到栈为空或peek的元素高于该值，也只有这样才能维护栈的单调性。
经典题的变形，从一个普通数组寻找下一个更大值，变为循环数组，寻找下一个更大值，同样并不复杂，只是在遍历数组时有点考究，正常情况下，遍历一遍数组就完成了，栈中剩下的是有序的降序数组，但本题要求循环，那么只需要再走一遍数组即可，最后栈中只会剩下一个数，即这个数组的最大值。
场景二：矩阵
矩阵求最大面积问题是单调栈问题的另一种典型应用，但问题相对都比较复杂，要考虑的因素较多，在进栈和出栈上的条件也更复杂一些。
简单概述一下题目，给一个数组，将每个值作为高度，那么获得这个数组构成的最大矩形。
这个题其实一开始没有接触过的话，很难会把这个和单调栈联系起来。其是遍历数组中的元素，对每个元素，分别获取左侧第一个小于当前值的索引和右侧第一个小于当前值的索引，就能够得到“以当前值作为矩形高”的矩形的面积最大值，最后进行一个矩形面积的比较，即可得到最大的矩形。这是比较好理解的，主要在于能不能想到这里。
接下来就根据等价的问题，分别从左和从右遍历一次，注意要维护一个边界，数组起点-1和数组终点n。得到两个数组，位置i分别记录了左侧第一个小于当前值的索引和右侧第一个小于当前值的索引。对这两个数组遍历，维护一个最大矩形面积即可。
2. 85. 最大矩形
这个题我认为其实是上一题的进阶，其依然属于最大矩形问题，主要的问题在于，如何把这个问题转化成上一个问题。我的思路是：遍历每一行，计算以当前行为底的柱状图中最大矩形面积，并维护一个最大矩形面积即可。这样的转化一定能够包含所有的情况，因为最大矩形必然可以为一个以某一行为底的柱状图所包含。
上一步中，需要得到每一行中各个列的高度，这个比较好判断：如果当前行是0，那列高度就为0；如果行不为0，那么高度为上一行该列高度+1
场景三：子数组问题
这类问题一般是求子数组的最值问题的，这类问题的核心在于用单调栈来得到一个数字在多大的范围内为最大值/最小值
显而易见的是，如果一个元素在某一定范围内为最小值，那么在该范围内（包含该最小值）任意取子数组，最小值都为当前值，那么复杂的计算问题可以简化为如下：
遍历数组，对于每个元素，获取左侧第一个小于当前元素的位置和右侧第一个小于当前元素的位置，记当前元素为arr[i]，左侧位置为left，右侧位置为right，那么该范围内的所有子数组之和为arr[i]*(i-left)*(right-i),由因为每个位置作为中心位置，结合单调栈的大小关系必然互斥，可以作如此等价。
注意，有一个特殊情况需要讨论，如果出现相同的元素该怎么办？很容易出现范围重复的情况，因此需要做专门的区分，以一个数组为例[2,1,3,4,1]，显然，当遍历到第一个2时，我们希望其包含1-4，而不到最后一个2，而处理最后一个2时，我们希望可以包含前面的2（这个逻辑也可以反过来，一样的）。那么可以得出，从左侧进栈时，只有严格大于当前值，才可以进栈，而从右侧进栈时，大于等于当前值都能够进栈。
这个问题是求所有子数组的最小值之和，包含的数量可能很大，所以要取余。注意每次计算都要把结果定义为long，否则会出问题
场景四：最小字典序
这类问题的一般思路是单调栈+贪心
移除k个数字，使得剩下的数字保证最大字典序
可以用经典的单调栈方法解决，维护一个单调递增的单调栈，每弹出一个元素，K的值就减一，直到K=0。由于是从最高位开始，可以用贪心的方法进行移除。
构造一个长度为k的数组，可以将问题拆分为从第一个数组构造一个长度为x的子序列，从第二个数组构造一个长度为y的子序列，并满足x+y=n，并按照字典序来对两个子序列进行排列，得到当前结果。那么当前的问题转化为：如何得到一个数组长度为x的最大字典序的子数组？
这个问题其实已经和上一个问题非常接近了，上一个问题是移除，这个问题是取，其实都是一个意思。同样可以维护一个单调栈（可以直接用数组存储），用remain来记录还有几个元素可选，top记录已经选了几个元素，对于每个位置，先循环判断remain是否大于0且当前值大于弹出的值。
for (int i = 0; i < length; i++) {
int num = nums[i];
while (top >= 0 && stack[top] < num && remain > 0) {
top--;
remain--;
}
if (top < k - 1) {
stack[++top] = num;
} else {
remain--;
}
}