单调栈

使用场景

单调栈解决的问题是：
【单调递减栈】对于一个数组中每一个数，求左边离他近的比他大的和右边离他近的比他大的数；
【单调递增栈】对于一个数组中每一个数，求左边离他近的比他小的和右边离他近的比他小的数。
同时时间复杂度O(n)，单调减栈栈底到栈顶单调递减，从大到小，递增相反。

【分析】只分析单调减栈，单调增栈同理。（栈内只放下标，比较大小时只需由下标检索）
数组从左往右遍历，大的数放下面，如果遇到一个数比栈顶的数大，则栈顶的数出栈，此时他的右边最近比他大的数就是让他出栈的数，而他左边最近比他大的数就是他栈内下方紧挨着的那个数。
如果下方为空，则左边没有比他大的数；如果没有数让它出栈，说明数组遍历结束，右方没有比他大的数。
【ps】如果遇到连续相等的数，则把序号压在一起放入栈内（链表）。

【举例】5（0）4（1）3（2）6（3）后面括号代表所属位置。

5（0）压入栈然后4（1）比5（0）小，所以将4（1）压入栈中第三步因为3（2）比4（1）小，所以也压入栈中
6（3）比3（2）要大，此时弹出栈顶的值3（2），并且将括号内的角标改成3变成3（3），代表对于3（2）这个数而言，右边第一个比他大的数位于3的位置。
3（2）左边离他最近的比他大的值就是在3的栈中的下一个值，也就是4（1）。
比较完之后将当前的6（3）放入数组之中，之前获得了信息的值可以直接进行表示了，不需要再放入栈中。
等到最后栈中还存在内容，则此时的所有数据单独弹出，此时右边没有比他大的数，栈中下面的数值是他的左边的比他大的数值。
如果出现相等数的情况，则此时下标压在一起，弹出是也一起弹出，多次计算。(链表实现)
由于每个数都是进栈一次出栈一次，所以复杂度为O(N)。

例题

构造数组的MaxTree

左神算法进阶班笔记Part2：单调栈
【解法】
1、大根堆（O(n)创建堆）
2、单调栈

柱状图最大矩阵面积

左神算法进阶班笔记Part2：单调栈
【思路】找到每一个根柱左边第一个比它小和右边第一个比它小的柱子（单调递增栈），根据距离可以求出该柱子所所在矩形的最大面积，从左往右依次遍历每一根柱子。最大值就是答案。
【TIP】在数组最右添加0，则可以省略数组遍历结束需要对栈内残留元素单独分析的情况，因为0肯定是最小数（需要放在栈底，把之前所有数出栈），同时0不影响结果面积。