leetcode---Trapping Rain Water

浏览数：47 / 时间：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.

 1 public class Solution {
 2     public int trap(int[] A) {
 3         int max = 0;
 4         if(A.length > 1){
 5             int[] result = new int[A.length];
 6             result[0] = 0;
 7             result[1] = 0;
 8             int largest = (A[0] <= A[1])? A[1]: A[0];
 9             int largestIndex = (A[0]<= A[1])? 1 : 0;
10             for(int i = 2; i < A.length; ++i){
11                 int length = 0;
12                 int sum = 0;
13                 for(int j = i - 1; j > largestIndex; --j){
14                     if(A[j] < A[i]){
15                         ++length;
16                         sum += A[j];
17                     }
18                     else
19                         break;
20                 }
21                 if(length == 0)
22                     result[i] = result[i - 1];
23                 else
24                     result[i] = Math.min(A[i], A[i - length - 1]) * length - sum + result[i - length - 1] ;
25                 largest = (A[i] <= largest)? largest: A[i];
26                 if(largest == A[i])
27                     largestIndex = i;
28             }
29             max = result[A.length - 1];
30         }
31         return max;
32     }
33 }