Trapping Rain Water

每个位置的水量 = 左右最大值中较小的一个 - 这个位置的高度

 1 public class Solution {
 2     public int trap(int[] A) {
 3         // IMPORTANT: Please reset any member data you declared, as
 4         // the same Solution instance will be reused for each test case.
 5         if(A == null)
 6             return 0;
 7         int result = 0;
 8         for(int i=0;i < A.length - 1; i++)
 9         {
10             int tmp = Math.min(max(A, 0, i), max(A, i+1, A.length)) - A[i];
11             if(tmp > 0)
12                 result += tmp;
13         }
14         return result;
15     }
16     private int max(int[] A, int start, int end)
17     {
18         int result = 0;
19         for(int i = start; i < end; i++)
20         {
21             if(A[i] > result)
22                 result = A[i];
23         }
24         return result;
25     }
26 }