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.

TRW

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*m)的解法：计算每一行可以积存的雨水量。其中m是height数组中的最大值。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
	int trap(vector<int>& height) {
	    if (height.size() == 0)
	        return 0;
		int sum = 0;
		/* A TLE Solution
		int MAX = 0;
		for (int i = 0; i < height.size(); ++i) {
		    if (height[i] > MAX) MAX = height[i];
		}

		queue<int> q;
		for (int i = 0; i < MAX; ++i) {
			while(q.size()) q.pop();
			for (int j = 0; j < height.size(); ++j) {
				if (height[j] >= i) q.push(j);
				if (q.size() == 2) {
				  int s = q.front();
				  int e = q.back();
				  sum += (e - s - 1);
				  q.pop();
				}
			}
		}
		*/

		// AC Solution
		vector<int> left(height.size(),0);
		vector<int> right(height.size(), 0);
		left[0] = height[0];
		right[height.size() - 1] = height[height.size() - 1];

		for (int i = 1; i < height.size(); ++i) {
			if (height[i] < left[i - 1])
				left[i] = left[i - 1];
			else
				left[i] = height[i];
		}

		for (int i = height.size() - 2; i >= 0; --i) {
			if (height[i] < right[i + 1])
				right[i] = right[i + 1];
			else
				right[i] = height[i];
		}

		for (int i = 0; i < height.size(); ++i) {
			sum += ((left[i] > right[i] ? right[i] : left[i]) - height[i]);
		}

		return sum;
	}
};