42.接雨水

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

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

1.双指针法

解题关键在于思考，height[i]这个位置上能够接多少雨水？它等于 i 这个位置左边最大高度和右边最大高度之间的最小值减去当前高度。因此问题就转化为了求解每个位置上左边最大高度和右边最大高度。

• 第一次for右往左遍历，记录下每个节点右边的最大值，并开辟一个数组保存在其中。第二次for左往右遍历找出每个节点左边的最大值，并计算面积。

• 用双指针，当前节点能接多少雨水取决于左右两边最大值的最小值，设置左指针left和右指针right，通过左指针维护左边最大值leftmax,右指针维护右边最大值。当leftmax<rightmax,就可以判断left位置节点能接多少水了，此时虽然rightmax不一定是left节点的右边最大值，但是leftmax一定是它的左边最小值(因为指针从边界开始维护)，并且leftmax一定是小于left节点右边最大值。left节点确定后，再向右移动。这里比较难想到的是每次确定结果的位置是在指针的一侧，而不需要left和right相碰。

2.单调栈

维护一个自栈底到栈顶元素依次递减的单调栈，栈内保存每个索引元素的下标。

根据当前元素若大于栈顶元素，则计算蓄水面积。每次计算雨水面积时栈内大小至少为2：

• 出栈，计算蓄水深度depth
• 读取当前栈顶元素索引，计算蓄水宽度width

可以发现，单调栈的做法每次计算的雨水区域都是一个矩形区域，计算时只依赖于栈内保存的左右边界索引，从而得到长方形的宽，即使某个元素出栈了也不会影响在该位置上可蓄水面积的计算。

class Solution {
    public int trap(int[] height) {
        int res=0;
        int max=Integer.MIN_VALUE;
        Stack<Integer> stack=new Stack<>();
        stack.push(0);
        for(int i=1;i<height.length;i++){
            while(stack.size()>0&&height[stack.peek()]<=height[i]){
                    int currinx=stack.pop();
                    if(stack.size()==0) break;
                    int depth=Math.min(height[i],height[stack.peek()])-height[currinx];
                    res+=(i-stack.peek()-1)*depth;
            }
            stack.push(i);
        }
        return res;
    }
}