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.
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
Analysis:
We first find out the max height in the array, then we start from the leftmost bar which is considered as the wall of the container. If there is a bar whose height is less than the wall, water will be saved above that bar. We do the same operation from rightmost to the highest bar position.
1 public class Solution { 2 /** 3 * @param heights: an array of integers 4 * @return: a integer 5 */ 6 public int trapRainWater(int[] A) { 7 if (A == null || A.length <= 2) return 0; 8 int maxIndex = 0; 9 for (int i = 1; i < A.length; i++) { 10 if (A[i] > A[maxIndex]) { 11 maxIndex = i; 12 } 13 } 14 int leftMax = A[0]; 15 int total = 0; 16 for (int i = 1; i < maxIndex; i++) { 17 if (A[i] < leftMax) { 18 total += (leftMax - A[i]); 19 } else { 20 leftMax = A[i]; 21 } 22 } 23 int rightMax = A[A.length - 1]; 24 for (int i = A.length - 2; i > maxIndex; i--) { 25 if (A[i] < rightMax) { 26 total += (rightMax - A[i]); 27 } else { 28 rightMax = A[i]; 29 } 30 } 31 return total; 32 } 33 }
原文：http://www.cnblogs.com/beiyeqingteng/p/5669106.html