“Offer 驾到,掘友接招!我正在参加2022春招打卡活动点击查看活动详情。
42. 接雨水
给定 n 个非负整数表明每个宽度为 1 的柱子的高度图,核算按此摆放的柱子,下雨之后能接多少雨水。
示例 1:
输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解说:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表明的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表明雨水)。
示例 2:
输入:height = [4,2,0,3,2,5]
输出:9
提示:
n == height.length
0 <= n <= 3 * 10^4
0 <= height[i] <= 10^5
思路一:暴力
对于第i个柱子,其左边柱子最高为l,右边柱子最高为r,则第i个柱子能接的雨水量为min(l,r) – height[i]。
遍历一切柱子,分别核算每个柱子能接到的雨水量,并求和。
C++版别 |
class Solution {
public:
int trap(vector<int>& height) {
int ans = 0,n = height.size();
for(int i = 1; i < n - 1; i++){
int l = 0, r = 0;
for(int j = i; j >= 0; j--){
l = max(l,height[j]);
}
for(int j = i; j < n; j++){
r = max(r,height[j]);
}
ans += min(l,r) - height[i];
}
return ans;
}
};
思路二:优化思路一,预处理出当前柱子左右两边的最高的柱子的高度值。
C++版别 |
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size(),ans = 0;
if(n == 0) return 0;
vector<int> l(n,0),r(n,0);
l[0] = height[0];
for(int i = 1; i < n; i++){
l[i] = max(height[i],l[i - 1]);
}
r[n - 1] = height[n - 1];
for(int i = n - 2; i >= 0; i--){
r[i] = max(height[i],r[i + 1]);
}
for(int i = 1; i < n - 1; i++){
ans += min(l[i],r[i]) - height[i];
}
return ans;
}
};
思路三:双指针
-
从思路二可知,只需
r_max > l_max
,积水高度将由l_max
决议,只需r_max < l_max
,积水高度将由r_max
决议; - 所以如果一边(右边)有更高的条形块,积水的高度依赖于从左到右的高度,反之亦然。
C++版别 |
class Solution {
public:
int trap(vector<int>& height) {
int l = 0,r = height.size() - 1,ans = 0;
int l_mx = 0,r_mx = 0;
while(l < r){
if(height[l] < height[r]){
if(height[l] > l_mx) l_mx = height[l];
else ans += l_mx - height[l];
l++;
}else{
if(height[r] > r_mx) r_mx = height[r];
else ans += r_mx - height[r];
r--;
}
}
return ans;
}
};
思路四:单调栈
- 保护一个单调递减栈,当有元素需求弹出时,说明现已形成了低洼,此时核算当前的低洼的高度并累加到成果中即可。
C++版别 |
class Solution {
public:
int trap(vector<int>& height) {
int ans = 0, n = height.size();
if(n == 0) return 0;
stack<int> st;
for(int i = 0; i < n; i++){
while(st.size() and height[st.top()] < height[i]){
int cur = st.top();
st.pop();
if(st.size()) ans += (i - st.top() - 1) * (min(height[i],height[st.top()]) - height[cur]);
}
st.push(i);
}
return ans;
}
};