[Leetcode][42. 接雨水] 5种解法：木桶原理，按行求，动态规划，双指针，单调栈
By Long Luo
Leetcode 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\)
- \(1 \le n \le 2 \cdot 10^4\)
- \(0 \le height[i] \le 10^5\)
方法一： 按列求（木桶原理）
思路与算法：
很容易想到，装水的多少，根据木桶原理，只需要关注左边最高的木板和右边最高的模板中较矮的一个就够了，那么存储的水，等于两边木板的较小值减去当前高度的值。
- 从左向右遍历数组：
- 从当前元素向左扫描并更新：\(\text{max_left}=\max(\text{max_left}, \text{height}[j])\)
- 从当前元素向右扫描并更新：\(\text{max_right}=\max(\text{max_right}, \text{height}[j])\)
- 更新 \(\text{ans} += \min(\text{max_left}, \text{max_right}) - \text{height}[i]\) 。
代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23public static int trap(int[] height) {
if (height == null || height.length <= 2) {
return 0;
}
int ans = 0;
int len = height.length;
for (int i = 1; i < len - 1; i++) {
int maxRight = 0;
int maxLeft = 0;
for (int right = i; right < len; right++) {
maxRight = Math.max(maxRight, height[right]);
}
for (int left = i; left >= 0; left--) {
maxLeft = Math.max(maxLeft, height[left]);
}
ans += Math.min(maxLeft, maxRight) - height[i];
}
return ans;
}
复杂度分析：
- 时间复杂度：\(O(n^2)\) ，遍历每一列需要 \(n\)，找出左边最高和右边最高的木板加起来刚好又是一个 \(n\) ，所以是 \(n^2\) 。
- 空间复杂度：\(O(1)\) 。
方法二：按行求
思路与算法：
求第 \(i\) 层的水，遍历每个位置，如果当前的高度小于 \(i\)，并且两边有高度大于等于 \(i\) 的，说明这个地方一定有水，水就可以加 \(1\)。
如果求高度为 \(i\) 的水，首先用一个变量 \(water\) 保存当前累积的水，初始化为 \(0\)。从左到右遍历墙的高度，遇到 \(h \ge i\) 的时候，开始更新 \(water\) 。
第一次遇到已经开始计算时并且 \(h < i\) 的就把 \(water+1\) ，再次遇到 \(h \ge i\) 的，说明这个地方一定有水，就把 \(water\) 加到最终的答案 \(ans\) 里， \(water=0\) ， \(flag=false\) ，然后继续循环。
代码如下所示：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
31public static int trap_row(int[] height) {
if (height == null || height.length <= 2) {
return 0;
}
int ans = 0;
int len = height.length;
int maxHeight = 0;
for (int x : height) {
maxHeight = Math.max(maxHeight, x);
}
for (int i = 1; i <= maxHeight; i++) {
boolean flag = false;
int water = 0;
for (int j = 0; j < len; j++) {
if (flag && height[j] < i) {
water++;
}
if (height[j] >= i) {
ans += water;
water = 0;
flag = true;
}
}
}
return ans;
}
复杂度分析：
- 时间复杂度：\(O(maxHeight \times n)\) ，其中 \(maxHeight\) 是数组元素的最大值。
- 空间复杂度：\(O(1)\) 。