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.

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

参考：

http://blog.csdn.net/doc_sgl/article/details/12307171

 1 public class Solution {
 2     public int trap(int[] A) {
 3         int waterSum = 0;
 4         int leftMaxHeight[] = new int[A.length];
 5         int rightMaxHeight[] = new int[A.length];
 6         
 7         int maxHeight = 0;
 8         for(int i = 0; i < A.length; i++){
 9             leftMaxHeight[i] = maxHeight;
10             maxHeight = maxHeight > A[i] ? maxHeight : A[i];
11         }//for
12         
13         maxHeight = 0;
14         for(int i = A.length - 1; i >= 0; i--){
15             rightMaxHeight[i] = maxHeight;
16             maxHeight = maxHeight > A[i] ? maxHeight : A[i];
17         }//for
18         
19         for(int i = 0; i < A.length; i++){
20             int minHeight = Math.min(leftMaxHeight[i], rightMaxHeight[i]);
21             int elementSum = minHeight - A[i];
22             if(elementSum > 0)
23                 waterSum += elementSum;
24         }//for
25         
26         return waterSum;
27     }
28     
29 }