Trapping Rain Water

接雨水

题目

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

解析重点

1.两种思路。第一种，什么样的地方可以蓄水，两个极值点之间，也就是我们循环数组，不断找出极值点，然后计算他们之间的蓄水面积即可。蓄水面积
怎么求呢，等于sum((min(a[i],a[j])-a[k])>0?(min(a[i],a[j])-a[k]):0).
2.第二种，一个位置可以蓄的水，依赖于他两边的极大值中极小值，那我们可以从数组两边向中间循环，极小值属于哪边，那我们就可以计算哪边的蓄水
量，trapWater=min(left,right)-a[i],当trapWater>0时，代表可以蓄水，累加即可。

java代码

这里实现的是第二种

class Solution {
    public int trap(int[] A){
        int a=0;
        int b=A.length-1;
        int max=0;
        int leftmax=0;
        int rightmax=0;
        while(a<=b){//左右两边循环，计算两边的最大值
            leftmax=Math.max(leftmax,A[a]);//左边的最大值
            rightmax=Math.max(rightmax,A[b]);//右边的最大值
            if(leftmax<rightmax){//如果左边比右边小
                max+=(leftmax-A[a]);//那么，左边当前的点的蓄水量可以计算
                a++;
            }
            else{
                max+=(rightmax-A[b]);//同左边
                b--;
            }
        }
        return max;
    }
}