[leetcode]Trapping Rain Water

新博文地址：[leetcode]Trapping Rain Water

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.

[picture]

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!

 这道题目我想复杂了，或者说不够聪明，没想到这么巧的方法，看到同学的算法，艾玛，高大上，理解起来，直观简单，代码少的很。

算法思想：

找到这个水池的台柱子（最高的柱子），然后以台柱子为中心，左边、右边向中间看齐。

【遍历左半段】先将开头的柱子高记录下来begin，向中间走，遇到比begin低的，求出落差，遇到比begin高的，更新begin。遇到中间的擎天柱，stop。

【遍历右半段】同上

时间复杂度O(n)，空间复杂度O(1)，掉渣天啊

即，我们只能向高处走，如果向地处走，这方法就不灵了。道理自己想

代码如下：

	public int trap(int[] a){
	    if(a == null || a.length <= 1){
	        return 0;
	    }
	    int max = 0;
	    int maxIndex = 0;
	    for(int i = 0; i < a.length; i++){
	        if(a[i] > max){
	            maxIndex = i;;
	            max = a[i];
	        }
	    }
	    int begin = a[0];
	    int sum = 0;
	    for(int i = 1 ; i < maxIndex; i++){
	        if(a[i] < begin){
	            sum += begin - a[i];
	        }else{
	            begin = a[i];
	        }
	    }
	    begin = a[a.length - 1];
	    for(int i = a.length - 2; i > maxIndex; i--){
	        if(a[i] < begin){
	            sum += begin - a[i];
	        }else{
	            begin = a[i];
	        }
	    }
	    return sum;
	}

 终于刷到100道了。tag一下