第六章 - 高频考题(困难)
0042. 接雨水

题目地址(42. 接雨水)

题目描述

1
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
Copied!
42.trapping-rain-water-1
1
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 感谢 Marcos 贡献此图。
2
3
示例:
4
5
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
6
输出: 6
Copied!

前置知识

  • 空间换时间
  • 双指针
  • 单调栈

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

双数组

思路

这是一道雨水收集的问题, 难度为hard. 如图所示,让我们求下过雨之后最多可以积攒多少的水。
如果采用暴力求解的话,思路应该是 height 数组依次求和,然后相加。
  • 伪代码
1
for (let i = 0; i < height.length; i++) {
2
area += (h[i] - height[i]) * 1; // h为下雨之后的水位
3
}
Copied!
问题转化为求 h,那么 h[i]又等于左右两侧柱子的最大值中的较小值,即 h[i] = Math.min(左边柱子最大值, 右边柱子最大值)
如上图那么 h 为 [0, 1, 1, 2, 2, 2 ,2, 3, 2, 2, 2, 1]
问题的关键在于求解左边柱子最大值右边柱子最大值, 我们其实可以用两个数组来表示leftMax, rightMax, 以 leftMax 为例,leftMax[i]代表 i 的左侧柱子的最大值,因此我们维护两个数组即可。

关键点解析

  • 建模 h[i] = Math.min(左边柱子最大值, 右边柱子最大值)(h 为下雨之后的水位)

代码

  • 代码支持: JS, Python3, C++:
JS Code:
1
/*
2
* @lc app=leetcode id=42 lang=javascript
3
*
4
* [42] Trapping Rain Water
5
*
6
*/
7
/**
8
* @param {number[]} height
9
* @return {number}
10
*/
11
var trap = function (height) {
12
let max = 0;
13
let volume = 0;
14
const leftMax = [];
15
const rightMax = [];
16
17
for (let i = 0; i < height.length; i++) {
18
leftMax[i] = max = Math.max(height[i], max);
19
}
20
21
max = 0;
22
23
for (let i = height.length - 1; i >= 0; i--) {
24
rightMax[i] = max = Math.max(height[i], max);
25
}
26
27
for (let i = 0; i < height.length; i++) {
28
volume = volume + Math.min(leftMax[i], rightMax[i]) - height[i];
29
}
30
31
return volume;
32
};
Copied!
Python Code:
1
class Solution:
2
def trap(self, heights: List[int]) -> int:
3
n = len(heights)
4
l, r = [0] * n, [0] * n
5
ans = 0
6
for i in range(1, len(heights)):
7
l[i] = max(l[i - 1], heights[i - 1])
8
for i in range(len(heights) - 2, 0, -1):
9
r[i] = max(r[i + 1], heights[i + 1])
10
for i in range(len(heights)):
11
ans += max(0, min(l[i], r[i]) - heights[i])
12
return ans
Copied!
C++ Code:
1
int trap(vector<int>& heights)
2
{
3
if(heights == null)
4
return 0;
5
int ans = 0;
6
int size = heights.size();
7
vector<int> left_max(size), right_max(size);
8
left_max[0] = heights[0];
9
for (int i = 1; i < size; i++) {
10
left_max[i] = max(heights[i], left_max[i - 1]);
11
}
12
right_max[size - 1] = heights[size - 1];
13
for (int i = size - 2; i >= 0; i--) {
14
right_max[i] = max(heights[i], right_max[i + 1]);
15
}
16
for (int i = 1; i < size - 1; i++) {
17
ans += min(left_max[i], right_max[i]) - heights[i];
18
}
19
return ans;
20
}
Copied!
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(N)$

双指针

思路

上面代码比较好理解,但是需要额外的 N 的空间。从上面解法可以看出,我们实际上只关心左右两侧较小的那一个,并不需要两者都计算出来。具体来说:
  • 如果 l[i + 1] < r[i] 那么 最终积水的高度由 i 的左侧最大值决定。
  • 如果 l[i + 1] >= r[i] 那么 最终积水的高度由 i 的右侧最大值决定。
因此我们不必维护完整的两个数组,而是可以只进行一次遍历,同时维护左侧最大值和右侧最大值,使用常数变量完成即可。这是一个典型的双指针问题,
具体算法:
  1. 1.
    维护两个指针 left 和 right,分别指向头尾。
  2. 2.
    初始化左侧和右侧最高的高度都为 0。
  3. 3.
    比较 height[left] 和 height[right]
    • 3.1 如果 height[left] < height[right], 那么瓶颈在于 height[left],不需要考虑 height[right]
      • 3.1.1 如果 height[left] < left_max, 则当前格子积水面积为(left_max - height[left]),否则无法积水,即积水面积为 0。也可将逻辑统一为盛水量为 max(0, left_max - height[left])
      • 3.1.2 左指针右移一位。(其实就是左指针的位置的雨水量已经计算完成了,我们移动到下个位置用同样的方法计算)
    • 3.2 否则 瓶颈在于 height[right],不需要考虑 height[left]
      • 3.2.1 如果 height[right] < right_max, 则当前格子积水面积为(right_max - height[left]),否则无法积水,即积水面积为 0。也可将逻辑统一为盛水量为 max(0, right_max - height[right])
      • 3.2.2 右指针右移一位。(其实就是右指针的位置的雨水量已经计算完成了,我们移动到下个位置用同样的方法计算)

代码

  • 代码支持: Python, C++, Go, PHP:
Python Code:
1
class Solution:
2
def trap(self, heights: List[int]) -> int:
3
n = len(heights)
4
l_max = r_max = 0
5
l, r = 0, n - 1
6
ans = 0
7
while l < r:
8
if heights[l] < heights[r]:
9
if heights[l] < l_max:
10
ans += l_max - heights[l]
11
else:
12
l_max = heights[l]
13
l += 1
14
else:
15
if heights[r] < r_max:
16
ans += r_max - heights[r]
17
else:
18
r_max = heights[r]
19
r -= 1
20
return ans
Copied!
C++ Code:
1
class Solution {
2
public:
3
int trap(vector<int>& heights)
4
{
5
int left = 0, right = heights.size() - 1;
6
int ans = 0;
7
int left_max = 0, right_max = 0;
8
while (left < right) {
9
if (heights[left] < heights[right]) {
10
heights[left] >= left_max ? (left_max = heights[left]) : ans += (left_max - heights[left]);
11
++left;
12
}
13
else {
14
heights[right] >= right_max ? (right_max = heights[right]) : ans += (right_max - heights[right]);
15
--right;
16
}
17
}
18
return ans;
19
}
20
21
};
Copied!
Go Code:
1
func trap(height []int) int {
2
if len(height) == 0 {
3
return 0
4
}
5
6
l, r := 0, len(height)-1
7
lMax, rMax := height[l], height[r]
8
ans := 0
9
for l < r {
10
if height[l] < height[r] {
11
if height[l] < lMax {
12
ans += lMax - height[l]
13
} else {
14
lMax = height[l]
15
}
16
l++
17
} else {
18
if height[r] < rMax {
19
ans += rMax - height[r]
20
} else {
21
rMax = height[r]
22
}
23
r--
24
}
25
}
26
return ans
27
}
Copied!
PHP Code:
1
class Solution
2
{
3
4
/**
5
* @param Integer[] $height
6
* @return Integer
7
*/
8
function trap($height)
9
{
10
$n = count($height);
11
if (!$n) return 0;
12
13
$l = 0;
14
$l_max = $height[$l];
15
$r = $n - 1;
16
$r_max = $height[$r];
17
$ans = 0;
18
while ($l < $r) {
19
if ($height[$l] < $height[$r]) {
20
if ($height[$l] < $l_max) $ans += $l_max - $height[$l];
21
else $l_max = $height[$l];
22
$l++;
23
} else {
24
if ($height[$r] < $r_max) $ans += $r_max-$height[$r];
25
else $r_max = $height[$r];
26
$r--;
27
}
28
}
29
return $ans;
30
}
31
}
Copied!
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(1)$

相关题目

更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。