[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.

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!

解题思路：

1、我的办法：两边夹的思想，若左边小于右边，则移动左边的指针，否则移动右边的指针。同时，若移动的指针小于上一个最小高度，则容量减去该移动指针此时所指的高度。若移动的指针和未移动的指针都大于此前最小高度，则加上超出的部分。说的不明白，代码比较好理解：

class Solution {
public:
	int trap(vector<int>& height) {
		int len = height.size();
		if (len<3){
			return 0;
		}
		int start = 0, end = len - 1;
		int result = 0, minH = 0;

		minH = min(height[start], height[end]);
		result = minH * (end - start - 1);

		while (start<end - 1){
			if (height[start]<height[end]){
				start++;
				result = result - min(minH, height[start]);
			}
			else{
				end--;
				result = result - min(minH, height[end]);
			}
			if (height[start]>minH && height[end]>minH){
				result += min(height[start] - minH, height[end] - minH) * (end - start - 1); //加上超出的部分
				minH = min(height[start], height[end]);
			}
		}
		return result;
	}
};

class Solution {
public:
	int trap(vector<int>& height) {
		int len = height.size();
		if (len<3){
			return 0;
		}
		int maxL[len], maxR[len];
		
		int maxH = height[0];
		maxL[0] = 0;
		
		for(int i=1; i<len; i++){
		    maxL[i] = maxH;
		    maxH = max(maxH, height[i]);
		}
		
		maxH = height[len-1];
		maxR[len-1]=0;
		
		int result=0;
		
		for(int i=len-2; i>=0; i--){
		    maxR[i]=maxH;
		    maxH = max(maxH, height[i]);
		    
		    result +=max(0, min(maxL[i], maxR[i]) - height[i]);
		}
		
		return result;
	}
};