接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]

输出：6

解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

思路

可以使用单调栈来解这道题，感觉还是比较好理解的。

什么时候会出现凹槽呢？

可以看出，单调栈从栈底到栈顶应该是单调递减的，当将要入栈的元素大于栈顶时就出现了凹槽，这时只需要用左右下标之差再乘以深度就可以算出部分面积。

要注意的是，单调栈中只存放坐标，而单调递减是指坐标对应高度单调递减

更复杂的凹槽：

这样的凹槽要依次算出每层的面积

最终的处理逻辑：

每次将入栈元素i的高度height[i]与栈顶元素高度height[stack.peek()]相比较，如果大于栈顶元素高度，则将栈顶弹出作为底坐标bottom，获取左边柱子的坐标left=stack.peek()，再从左边柱子高度height[left]与入栈元素高度（右边柱子高度）height[i]中选出最小的高度减去底高度height[bottom]作为算部分面积的高度，i-left-1作为算部分面积的宽度，最后相乘得到部分面积，迭代直到栈顶元素不大于入栈元素。如果栈中弹出了底后没有元素了，就不进行面积计算了，直接将元素入栈进行下一个元素的入栈。

实现代码

class Solution {
    public int trap(int[] height) {
        int area=0;
        Deque<Integer> stack=new ArrayDeque<>();
        for(int i=0;i<height.length;i++) {
            while (!stack.isEmpty()&&height[i]>height[stack.peek()]) {
                //获取底部高度
                int bottom=height[stack.pop()];
                //获取左侧坐标和高度
                if(!stack.isEmpty()) {
                    int leftIndex=stack.peek();
                    int left=height[leftIndex];
                    //水深为左右取最小高度减去底部高度
                    int depth=Math.min(left,height[i])-bottom;
                    area+=depth*(i-leftIndex-1);
                }
            }
            stack.push(i);
        }
        return area;
    }
}