42. 接雨水

一 题目：

二 思路：

单调递增栈

三 代码：

 public int trap(int[] height) {

        int sum=0;

        //存放下一个大于等于自己的柱子,相邻的丢弃
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < height.length; i++) {
            //有高度差了,看看能计算几层水
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                //水底
                int low=stack.pop();
                //相同元素一并出栈
                while (!stack.isEmpty() &&height[ stack.peek()]==height[low]){
                    stack.pop();
                }

                //计算本层水
                if (!stack.isEmpty()){
                    //左边界
                    Integer left = stack.peek();
                    //高度差
                    int h=Math.min(height[left]-height[low],height[i]-height[low]);
                    int w=i-left-1;
                    sum+=h*w;
                }
            }
            stack.push(i);
        }

        return sum;
    }