[LeetCode]42. Trapping Rain Water

Problem

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.

rainwatertrap.png

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
2
3
Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

Solution

Analysis

题目给定一个非负数数组,每个数字表示当前的高度,要求计算下雨之后,这些凹陷位置能存储的雨水量. 针对每一个位置来说,如果只要是凹陷情况下,才有可能存储雨量, 也就是说只有当其左边的高度和右边的高度都大于当前位置的高度时,才有可能存储雨量.

了解上面之后,我的原始方法是通过统计所有连续(左右)的位置以及高度,然后计算面积. 但是这种方法太麻烦,无从下手.这题标为hard,并不是没有理由的.

看大佬解法. 最终答案通过逐个位置计算,遍历完所有答案之后,就可以得到答案. 所以现在的工作就是计算每个位置可能的雨水存储量, 这个量和当前位置的左右边界相关. 所以问题就变成,求解每个位置的左右边界,其实左右边界中也只能其中最小的边界有关.

一种方法是使用一个数据dp,记录dp[i]表示当前位置的左右边界的最小值, 求解时先从左到右记录左边界值(这时候取i之前的最大值), 然后从右到左记录右边界值,同时比较左右边界,将dp[i]表示为两者的最小值, 此外,比较dp[i]和当前高度height[i]比较,如果height低,说明可以存储雨量.

另一种方法是双指针法 :一个记录左边界,一个记录右边界,找到两个的较小值,移动这个指针,固定较大值,这样可以计算所有以较大值和较小值为边界的凹陷值,移动较小值时,如果当前高度小于较小值,说明可以存储雨量.

Code

方法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int trap(vector<int>& height) {
int result = 0, size = height.size(), mx = 0;//左边界的最大值
vector<int> dp(size, 0);

for (int i=0; i < size; i++){
dp[i] = mx;
mx = max(mx, height[i]);//更新左边界的最大值
}
mx = 0;//右边界的最大值
for (int i=size-1; i >= 0; i--){
dp[i] = min(dp[i], mx);//结果为左右边界的较小值.
mx = max(mx, height[i]);//更新右边界值
// 可以存储雨水
if (dp[i] > height[i]) result += dp[i] - height[i];
}

return result;
}
};

方法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int trap(vector<int>& height) {
int res = 0, l = 0, r = height.size() - 1;// 双指针
while (l < r) {
int mn = min(height[l], height[r]);
if (mn == height[l]) {// 左边界
++l;
while (l < r && height[l] < mn) {//可以存储雨水量
res += mn - height[l++];
}
} else {// 右边界
--r;
while (l < r && height[r] < mn) {
res += mn - height[r--];
}
}
}
return res;
}
};

References

https://www.cnblogs.com/grandyang/p/4402392.html

您的支持就是我更新的最大动力!谢谢!