[Leetcode][42. 接雨水] 5种解法:木桶原理,按行求,动态规划,双指针,单调栈

By Long Luo

Leetcode 42. 接雨水 题目如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
42. 接雨水

给定$n$个非负整数表示每个宽度为$1$的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

示例 1:

![接雨水 1](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/10/22/rainwatertrap.png)

输入: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 <= n <= 2 * 10^4
0 <= height[i] <= 10^5

方法一: 按列求(木桶原理)

思路与算法:

很容易想到,装水的多少,根据木桶原理,只需要关注左边最高的木板和右边最高的模板中较矮的一个就够了,那么存储的水,等于两边木板的较小值减去当前高度的值。

  1. 从左向右遍历数组:
    • 从当前元素向左扫描并更新:max_left=max(max_left,height[j])\text{max\_left}=\max(\text{max\_left}, \text{height}[j])
    • 从当前元素向右扫描并更新:max_right=max(max_right,height[j])\text{max\_right}=\max(\text{max\_right}, \text{height}[j])
  2. 更新 ans+=min(max_left,max_right)height[i]\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
23
public 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(n2)O(n^2),遍历每一列需要 nn,找出左边最高和右边最高的木板加起来刚好又是一个 nn,所以是 n2n^2
  • 空间复杂度:O(1)O(1)

方法二:按行求

思路与算法:

求第 ii 层的水,遍历每个位置,如果当前的高度小于 ii,并且两边有高度大于等于 ii 的,说明这个地方一定有水,水就可以加 11

如果求高度为 ii 的水,首先用一个变量 waterwater 保存当前累积的水,初始化为 00。从左到右遍历墙的高度,遇到 hih \ge i 的时候,开始更新 waterwater

第一次遇到已经开始计算时并且 h<ih < i 的就把 water+1water+1,再次遇到 hih \ge i 的,说明这个地方一定有水,就把 waterwater 加到最终的答案 ansans 里,water=0water=0flag=falseflag=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
31
public 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×n)O(maxHeight \times n),其中 maxHeightmaxHeight 是数组元素的最大值。
  • 空间复杂度:O(1)O(1)

方法三:动态规划

思路与算法:

方法一中对于每一列,我们求它左边最高的木板和右边最高的木板,都需要遍历一遍所有高度,这里可以优化一下。

我们使用两个数组,leftMax[i]leftMax[i] 代表第 ii 列左边最高的木板的高度,rightMax[i]rightMax[i] 代表第 ii 列右边最高的木板的高度,注意这里第 ii 列左(右)边最高的木板,是不包括自身的。

leftMax[i]=Max.max(leftMax[i1],height[i1])leftMax[i] = Max.max(leftMax[i-1], height[i-1]),当前列左边最高的木板要么是它左边的木板,要么是左边木板左边的最高高度。

同理 rightMax[i]=Math.max(maxright[i+1],height[i+1])rightMax[i] = Math.max(max_right[i+1], height[i+1])

代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static int trap_dp(int[] height) {
if (height == null || height.length <= 2) {
return 0;
}

int ans = 0;
int len = height.length;
int[] leftMax = new int[len];
int[] rightMax = new int[len];
for (int i = 1; i < len - 1; i++) {
leftMax[i] = Math.max(leftMax[i - 1], height[i - 1]);
}

for (int i = len - 2; i >= 0; i--) {
rightMax[i] = Math.max(rightMax[i + 1], height[i + 1]);
}

for (int i = 1; i < len - 1; i++) {
int min = Math.min(leftMax[i], rightMax[i]);
ans += min > height[i] ? min - height[i] : 0;
}

return ans;
}

复杂度分析:

  • 时间复杂度:O(n)O(n)
  • 空间复杂度:O(n)O(n)

方法四:双指针

思路与算法:

一般来说,动态规划的空间复杂度都可以进行优化。从方法三也可以看出,leftMax[i]leftMax[i]rightMax[i]rightMax[i] 数组中的元素其实只用到了一次,所以可以只用一个元素就行了。

很容易写出如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int trap_tp(int[] height) {
if (height == null || height.length <= 2) {
return 0;
}

int len = height.length;
int ans = 0;
int leftMax = height[0];
int[] rightMax = new int[len];
for (int i = len - 2; i >= 0; i--) {
rightMax[i] = Math.max(rightMax[i + 1], height[i + 1]);
}

for (int i = 1; i < len - 1; i++) {
leftMax = Math.max(leftMax, height[i]);
int min = Math.min(leftMax, rightMax[i]);
ans += min > height[i] ? min - height[i] : 0;
}

return ans;
}

上述代码的空间复杂度还是 O(n)O(n),如何才能把 rightMaxrightMax 的数组也去掉呢?

因为从左往右处理到 ii 下标时,左边的最大值 leftMaxleftMax 是可信的,因为 rightMaxrightMax 是从右往左遍历的,所以需要 rightMaxrightMax 数组来记录右边最大值。

基于此,要用到两个指针,leftleftrightright,从两个方向去遍历。

如果一端有更高的木板,那么水的高度依赖于当前方向的高度(从左到右),而当我们发现另一侧(右侧)的木板不是最高的,则开始从相反的方向遍历(从右到左)。

我们可以只需要 11 次遍历,在遍历时同时维护 leftMax\text{leftMax}rightMax\text{rightMax},代码如下所示:

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
public static int trap_tp_opt(int[] height) {
if (height == null || height.length <= 2) {
return 0;
}

int len = height.length;
int ans = 0;
int left = 0;
int right = len - 1;
int leftMax = height[0];
int rightMax = height[right];
while (left < right) {
if (height[left] < height[right]) {
leftMax = Math.max(leftMax, height[left]);
ans += leftMax - height[left];
left++;
} else {
rightMax = Math.max(rightMax, height[right]);
ans += rightMax - height[right];
right--;
}
}

return ans;
}

复杂度分析:

  • 时间复杂度:O(n)O(n)
  • 空间复杂度:O(1)O(1)

方法五:单调栈

思路与算法:

遍历到某些木板的时候,会由于和之前的某个木板形成凹形的坑,从而可以接住雨水,所以这道题目可以用单调栈来做。

单调栈就是比普通的栈多一个性质,即维护一个栈内元素单调。使用单调栈来解,和方法二类似,但又有所区别。具体到这道题,单调栈存储的是下标,满足从栈底到栈顶的下标对应的 height[idx]\textit{height}[idx] 递减。

从左到右遍历数组,遍历到下标 ii 时,如果栈内至少有两个元素,记栈顶元素为 top\textit{top}top\textit{top} 的下面一个元素是 left\textit{left},则一定有 height[left]height[top]\textit{height}[\textit{left}] \ge \textit{height}[\textit{top}]。如果 height[i]>height[top]\textit{height}[i]>\textit{height}[\textit{top}] ,则得到一个可以接雨水的区域,该区域的宽度是 ileft1i-\textit{left}-1,高度是 min(height[left],height[i])height[top]\min(\textit{height}[\textit{left}], \textit{height}[i])-\textit{height}[\textit{top}],根据宽度和高度即可计算得到该区域能接的雨水量。

为了得到 left\textit{left},需要将 top\textit{top} 出栈。在对 top\textit{top} 计算能接的雨水量之后,left\textit{left} 变成新的 top\textit{top},重复上述操作,直到栈变为空,或者栈顶下标对应的 height\textit{height} 中的元素大于或等于 height[i]\textit{height}[i]

在对下标 ii 处计算能接的雨水量之后,将 ii 入栈,继续遍历后面的下标,计算能接的雨水量。遍历结束之后即可得到能接的雨水总量。

代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static int trap_stack_opt(int[] height) {
int ans = 0;
Deque<Integer> stack = new LinkedList<Integer>();
int len = height.length;
for (int i = 0; i < len; i++) {
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int top = stack.pop();
if (stack.isEmpty()) {
break;
}
int left = stack.peek();
int currWidth = i - left - 1;
int currHeight = Math.min(height[left], height[i]) - height[top];
ans += currWidth * currHeight;
}
stack.push(i);
}

return ans;
}

复杂度分析:

  • 时间复杂度:O(n)O(n)
  • 空间复杂度:O(n)O(n)

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗