【多解法】力扣42-接雨水

  |  

摘要: 接雨水问题的各种解法

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


本文我们看一个几年前就被网上研究透了的陈题:接雨水。不过从一题多解的角度,本题还是值得看一下的,几个算法都是非常主流的算法:

  • 算法1:单调栈
  • 算法2:动态规划
  • 算法3:双指针
  • 算法4:减治

$1 题目

给定 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

提示:

1
2
3
n == height.length
1 <= n <= 2 * 1e4
0 <= height[i] <= 1e5

$2 题解

算法1: 单调栈

单调栈的原理参考 单调栈

维护一个单调递减的栈:栈内保存的是下标 i,从栈底到栈顶,height[i] 单调递减。对于栈里相邻的两个下标,靠近栈底的下标是靠近栈顶的下标左侧第一个比它大的位置。

从小到大枚举下标 i,将栈里比 height[i] 小的下标弹出去,假设弹出的下标是 j,则可以更新一部分面积,宽度是栈里的下一个下标 k 与 i 的距离 (i - k - 1),高度是准备压入的 height[i] 与栈底 max_h 的较小值减去 height[j]。

每个下标都要经历一次进栈出栈,将每次出栈时更新的面积累加起来就得到答案。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int trap(vector<int>& height) {
if(height.empty()) return 0;
int n = height.size();
if(n <= 2) return 0;
stack<int> st;
int ans = 0;
for(int i = 0; i < n; ++i)
{
while(!st.empty() && height[st.top()] <= height[i])
{
int j = st.top();
st.pop();
if(st.empty())
break;
int k = st.top();
ans += (i - k - 1) * (min(height[k], height[i]) - height[j]);
}
st.push(i);
}
return ans;
}
};

算法2: 预处理前缀状态

对每个 i,预处理出:

1
2
lh[i]: i 左边的最高值
rh[i]: i 右边的最高值

预处理的过程是动态规划,转移方程如下:

1
2
lh[i] = max(lh[i - 1], h[i - 1]), max 有结合律,可以从左往右扫
rh[i] = max(rh[i + 1], h[i + 1]), 类似地, rh 从右往左扫

这种思路有点类似于前缀状态的预处理,只是这里的状态是前缀最值和后缀最值。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int trap(vector<int>& height) {
if(height.empty()) return 0;
int n = height.size();
if(n <= 2) return 0;
vector<int> lh(n, 0); // 0,[1..n],n+1
vector<int> rh(n, 0);
for(int i = 1; i <= n - 1; ++i)
lh[i] = max(lh[i - 1], height[i - 1]);
for(int i = n - 2; i >= 0; --i)
rh[i] = max(rh[i + 1], height[i + 1]);
int result = 0;
for(int i = 1; i < n - 1; ++i)
{
int hw = min(lh[i], rh[i]);
if(height[i] < hw)
result += hw - height[i];
}
return result;
}
};

算法3: 双指针

从两个端点向里收缩,维护左右端点指针l=0, r=n-1和左高右高。

收缩时向内推进高度较低的哪个指针,对比推进之后的值与推进之前的值。

如果变大了,则更新响应的左高或右高。

如果变小了,则推进之后的位置可以容纳雨水,高度就是当前左高右高中较小的。

二维接雨水问题的解法在思路上与一维的双指针做法相同。

代码 (C++)

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
class Solution {
public:
int trap(vector<int>& height) {
if(height.empty()) return 0;
int n = height.size();
if(n <= 2) return 0;
int lh = height[0], rh = height[n - 1];
int left = 0, right = n - 1;
int result = 0;
while(left < right)
{
if(lh <= rh) // 向右移动 left
{
++left;
if(height[left] < lh)
result += lh - height[left];
else if(height[left] > lh)
lh = height[left];
}
else // 向左移动 right
{
--right;
if(height[right] < rh)
result += rh - height[right];
else if(height[right] > rh)
rh = height[right];
}
}
return result;
}
};

算法4: 减治

1
2
3
4
5
6
7
8
原问题区间 [left, right] 

可以直接解决的情况: right - left <= 1 时可以直接解决,答案为 0

找到 [left, right] 上最大值位置 m1 和次大值位置 m2
[min(m1, m2), max(m1, m2)] 上的问题可以直接解决,答案为 (abs(m1 - m2) - 1) * A[m2]

减治: 子问题变为 [left, min(m1, m2)], [max(m1, m2), right]

代码 (C++)

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
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
return solve(height, 0, n - 1);
}

private:
int solve(const vector<int>& h, int l, int r)
{
if(r - l <= 1)
return 0;
int m1 = -1, m2 = -1;
int max1 = INT_MIN, max2 = INT_MIN;
for(int i = l; i <= r; ++i)
{
if(h[i] > max1)
{
max2 = max1;
m2 = m1;
max1 = h[i];
m1 = i;
}
else if(h[i] > max2)
{
max2 = h[i];
m2 = i;
}
}
int ans = (abs(m1 - m2) - 1) * max2;
for(int i = min(m1, m2) + 1; i <= max(m1, m2) - 1; ++i)
ans -= h[i];
ans += solve(h, l, min(m1, m2));
ans += solve(h, max(m1, m2), r);
return ans;
}
};

Share