【leetcode】Trapping Rain Water

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

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. Thanks Marcos for contributing this image!

题解：在网上研究了半天，才找到时间O(n)和空间O(1)的算法：

首先找出最大的bar，索引记录在totalMaxIndex这个变量里面；
从左往右，依次处理totalMaxIndex左边的bar；设置一个curMax记录遍历到当前为止最大的bar，那么对于A[i]，有两种可能：一是A[i]<curMax，那么这时候就可以储水(curMax - A[i])；而是A[i] > curMax，这时更新curMax = A[i]；
从右往左，依次处理totalMaxIndex右边的bar，方法同2.

具体算法过程如下图所示：

基本的原理就是当从左往右遍历的时候，最高的bar保证了能够在右端将水拦住，那么就只要计算对于A[i]，在左端能够拦截住多高的水就可以了，即变量curMax。

代码如下：

 1 public class Solution {
 2     public int trap(int[] A) {
 3         if(A == null || A.length == 0)
 4             return 0;
 5         
 6         int curMax = 0;
 7         int totalMax = A[0];
 8         int totalMaxIndex = 0;
 9         int answer = 0;
10         
11         for(int i = 1;i < A.length;i++){
12             if(A[i] > totalMax){
13                 totalMax = A[i];
14                 totalMaxIndex = i;
15             }
16         }
17         
18         for(int i = 0;i < totalMaxIndex;i++){
19             if(A[i] < curMax)
20                 answer += curMax - A[i];
21             else
22                 curMax = A[i];
23         }
24         
25         curMax = 0;
26         for(int i = A.length-1;i > totalMaxIndex;i--){
27             if(A[i] < curMax)
28                 answer += curMax - A[i];
29             else {
30                 curMax = A[i];
31             }
32         }
33         
34         return answer;
35     }
36 }