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.
1 public class Solution { 2 public int trap(int[] A) { 3 int len = A.length; 4 if(len<2) return 0; 5 int []leftMax = new int[len], rightMax = new int[len]; 6 int max=0; 7 max = A[0]; 8 leftMax[0] = 0; 9 for(int i=1;i<len;i++){ 10 leftMax[i] = max; 11 if(A[i]>max){ 12 max = A[i]; 13 } 14 } 15 max = A[len-1]; 16 rightMax[len-1]=0; 17 int trap = 0; 18 for(int i=len-2;i>=0;i--){ 19 rightMax[i] = max; 20 if(max<A[i]){ 21 max = A[i]; 22 } 23 if(Math.min(rightMax[i],leftMax[i])-A[i]>0){ 24 trap+=Math.min(rightMax[i],leftMax[i])-A[i]; 25 } 26 } 27 return trap; 28 } 29 }
原文：http://www.cnblogs.com/krunning/p/3539147.html
