一文弄懂单调栈（附示例和代码）

栈，先进后出的数据结构。

单调栈，顾名思义，是在栈的基础上增加了单调性。这就要求每传入一个数据，就需要和最新入栈的数据进行比较，符合单调性就入栈，否则就持续出栈，直到符合单调性，然后把该数据入栈。

举个例子，给出一个数组，[10,15,20,8,6,13,12,5]，依次入栈，要求单调递增

算法题应用（Leetcode接雨水问题），建议先自己写一遍，看看能否自己解决。

这道题就可以使用单调栈作为一种解题思路，举一个简单的示例数组[4,1,1,3]，看看我们解题需要什么数据。

要计算“雨水量”，我们需要知道两侧的墙壁高度，记作h1、h2，还需要知道宽度w，另外还有底b，这样我们就可以计算雨水容量capacity=[min(h1,h2)-b]×w，在这个示例中，也就是(3-1)×2=4

总结，要计算这个容积，需要知道两侧高度、底和宽度，而宽度可以使用数组的索引计算。

这道题按照单调栈（单调递减的栈）解题思路如下：

每当有数据出栈，就需要计算一次雨水量，两侧高度可以通过栈中相邻的两个数据获取到，底就是出栈的数据，宽度是索引之差。

现在来写程序。

class Solution {
    public int trap(int[] height) {
        int result = 0;
        //单调栈，在接雨水问题中，是单调递减的栈，存储数组的索引，不存储具体的数值
        List list = new ArrayList();
        //遍历数组
        for (int arrayIndex = 0; arrayIndex  0 && height[arrayIndex] >= height[list.get(list.size()-1)]){
                    if(list.size()>=2){
                        //两个边较低的值减去底，然后*宽度
                        result+=((Math.min(height[list.get(list.size()-2)], height[arrayIndex]) - height[list.get(list.size()-1)]) * (arrayIndex - list.get(list.size()-2) - 1));
                    }
                    list.remove(list.size()-1);
                }
                list.add(arrayIndex);
            }
        }
        return result;
    }
}

PS：这里的程序与我上面的描述有点出入，这里每次出栈都要计算一次雨水量，针对[4,1,1,3]这个数组，第一个1出栈的时候计算一次，雨水量是0；第二个1出栈的时候再计算一次，雨水量是4。