42.接雨水

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

示例 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 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

**输入：** height = [4,2,0,3,2,5]
**输出：** 9

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

方法一：第一遍遍历找出最高点。然后分别从左右遍历至最高点，边遍历边统计左右两侧最高点，统计每一列能接到的雨水数量

class Solution {
    public int trap(int[] height) {
        int ans=0,max=0;
        for(int i=0;i<height.length;i++){
            if(height[i]>height[max])
                max=i;
        }
        int temp=0;
        for(int k=0;k<max;k++){
            if(height[k]>temp)
                temp=height[k];
            ans+=(temp-height[k]);
        }
        temp=0;
        for(int k=height.length-1;k>max;k--){
            if(height[k]>temp)
                temp=height[k];
            ans+=(temp-height[k]);
        }
        return ans;
    }
}

方法二：同leetcode11，盛水最多的容器。左右指针遍历时记录下左右两边的最高处，统计矮的一侧的单条存水量，然后移动数值小的，因为矮的是短板

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
}