[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;
	}
};
2、网上另外一个比较好的办法是左右两边扫的办法。记录每个数左边和右边最大的数。左边最大与右边最大构成一个容器,减去本身的空间,这相当于这个位置上的台阶贡献了容量。

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;
	}
};


郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。