[LeetCode] 42. Trapping Rain Water 收集雨水

时间:2024-08-05 22:37:26

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.

[LeetCode] 42. Trapping Rain Water 收集雨水
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!

Example:

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

这道收集雨水的题跟之前的那道 Largest Rectangle in Histogram 有些类似,但是又不太一样,先来看一种方法,这种方法是基于动态规划 Dynamic Programming 的,维护一个一维的 dp 数组,这个 DP 算法需要遍历两遍数组,第一遍在 dp[i] 中存入i位置左边的最大值,然后开始第二遍遍历数组,第二次遍历时找右边最大值,然后和左边最大值比较取其中的较小值,然后跟当前值 A[i] 相比,如果大于当前值,则将差值存入结果,参见代码如下:

C++ 解法一:

class Solution {
public:
int trap(vector<int>& height) {
int res = , mx = , n = height.size();
vector<int> dp(n, );
for (int i = ; i < n; ++i) {
dp[i] = mx;
mx = max(mx, height[i]);
}
mx = ;
for (int i = n - ; i >= ; --i) {
dp[i] = min(dp[i], mx);
mx = max(mx, height[i]);
if (dp[i] > height[i]) res += dp[i] - height[i];
}
return res;
}
};

Java 解法一:

public class Solution {
public int trap(int[] height) {
int res = 0, mx = 0, n = height.length;
int[] dp = new int[n];
for (int i = 0; i < n; ++i) {
dp[i] = mx;
mx = Math.max(mx, height[i]);
}
mx = 0;
for (int i = n - 1; i >= 0; --i) {
dp[i] = Math.min(dp[i], mx);
mx = Math.max(mx, height[i]);
if (dp[i] - height[i] > 0) res += dp[i] - height[i];
}
return res;
}
}

再看一种只需要遍历一次即可的解法,这个算法需要 left 和 right 两个指针分别指向数组的首尾位置,从两边向中间扫描,在当前两指针确定的范围内,先比较两头找出较小值,如果较小值是 left 指向的值,则从左向右扫描,如果较小值是 right 指向的值,则从右向左扫描,若遇到的值比当较小值小,则将差值存入结果,如遇到的值大,则重新确定新的窗口范围,以此类推直至 left 和 right 指针重合,参见代码如下:

C++ 解法二:

class Solution {
public:
int trap(vector<int>& height) {
int res = , l = , r = height.size() - ;
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;
}
};

Java 解法二:

public class Solution {
public int trap(int[] height) {
int res = 0, l = 0, r = height.length - 1;
while (l < r) {
int mn = Math.min(height[l], height[r]);
if (height[l] == mn) {
++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;
}
}

我们可以对上面的解法进行进一步优化,使其更加简洁:

C++ 解法三:

class Solution {
public:
int trap(vector<int>& height) {
int l = , r = height.size() - , level = , res = ;
while (l < r) {
int lower = height[(height[l] < height[r]) ? l++ : r--];
level = max(level, lower);
res += level - lower;
}
return res;
}
};

Java 解法三:

public class Solution {
public int trap(int[] height) {
int l = 0, r = height.length - 1, level = 0, res = 0;
while (l < r) {
int lower = height[(height[l] < height[r]) ? l++ : r--];
level = Math.max(level, lower);
res += level - lower;
}
return res;
}
}

下面这种解法是用 stack 来做的,博主一开始都没有注意到这道题的 tag 还有 stack,所以以后在总结的时候还是要多多留意一下标签啊。其实用 stack 的方法博主感觉更容易理解,思路是,遍历高度,如果此时栈为空,或者当前高度小于等于栈顶高度,则把当前高度的坐标压入栈,注意这里不直接把高度压入栈,而是把坐标压入栈,这样方便在后来算水平距离。当遇到比栈顶高度大的时候,就说明有可能会有坑存在,可以装雨水。此时栈里至少有一个高度,如果只有一个的话,那么不能形成坑,直接跳过,如果多余一个的话,那么此时把栈顶元素取出来当作坑,新的栈顶元素就是左边界,当前高度是右边界,只要取二者较小的,减去坑的高度,长度就是右边界坐标减去左边界坐标再减1,二者相乘就是盛水量啦,参见代码如下:

C++ 解法四:

class Solution {
public:
int trap(vector<int>& height) {
stack<int> st;
int i = , res = , n = height.size();
while (i < n) {
if (st.empty() || height[i] <= height[st.top()]) {
st.push(i++);
} else {
int t = st.top(); st.pop();
if (st.empty()) continue;
res += (min(height[i], height[st.top()]) - height[t]) * (i - st.top() - );
}
}
return res;
}
};

Java 解法四:

class Solution {
public int trap(int[] height) {
Stack<Integer> s = new Stack<Integer>();
int i = 0, n = height.length, res = 0;
while (i < n) {
if (s.isEmpty() || height[i] <= height[s.peek()]) {
s.push(i++);
} else {
int t = s.pop();
if (s.isEmpty()) continue;
res += (Math.min(height[i], height[s.peek()]) - height[t]) * (i - s.peek() - 1);
}
}
return res;
}
}

Github 同步地址:

https://github.com/grandyang/leetcode/issues/42

类似题目:

Trapping Rain Water II

Container With Most Water

Product of Array Except Self

Pour Water

参考资料:

https://leetcode.com/problems/trapping-rain-water/

https://leetcode.com/problems/trapping-rain-water/discuss/17364/7-lines-C-C%2B%2B

https://leetcode.com/problems/trapping-rain-water/discuss/17414/A-stack-based-solution-for-reference-inspired-by-Histogram

https://leetcode.com/problems/trapping-rain-water/discuss/17357/Sharing-my-simple-c%2B%2B-code%3A-O(n)-time-O(1)-space

LeetCode All in One 题目讲解汇总(持续更新中...)