Trapping Rain Water

浏览数：17 / 时间：2015年06月11日

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.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

技术分享

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!

首先，挨个分析每个A[i]能trapped water的容量，然后将所有的A[i]的trapped water容量相加即可

其次，对于每个A[i]能trapped water的容量，取决于A[i]左右两边的高度（可延展）较小值与A[i]的差值，即volume[i] = [min(left[i], right[i]) - A[i]] * 1，这里的1是宽度，如果the width of each bar is 2,那就要乘以2了”

那么如何求A[i]的左右高度呢？要知道，能盛多少水主要看短板。那么对每个A[i]来说，要求一个最高的左短板，再求一个最高的右短板，这两个直接最短的板子减去A[i]原有的值就是能成多少水了。

所以需要两遍遍历，一个从左到右，找最高的左短板；一个从右到左，找最高的右短板。最后记录下盛水量的总值就是最终结果了。

package leetcode2;

public class TrappingRainWater {
    public static int Trapping(int[] A){
        if(A==null){
            return 0;
        }
        int maxvol=0;
        int lmax=0;
        int[] vol=new int[A.length];
        int[] left=new int[A.length];
        int[] right=new int[A.length];
        for(int i=0;i<A.length;i++){
            left[i]=Math.max(lmax, A[i]);
            lmax=Math.max(lmax,A[i]);
        }
        int rmax=0;
        for(int i=A.length-1;i>0;i--){
            right[i]=Math.max(rmax,A[i] );
            rmax=Math.max(rmax, A[i]);
        }
        for(int i=0;i<A.length;i++){
          vol[i]=1*(Math.min(left[i], right[i])-A[i]);
          if(vol[i]>0){
              maxvol=maxvol+vol[i];
          }
        }
        
        return maxvol;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
      int[] a={0,1,0,2,1,0,1,3,2,1,2,1};
      System.out.println(Trapping(a));
    }

}