【LeetCode】42. 接雨水

42. 接雨水（二维）

一、题目描述

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

上面是由数组 [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.1 按列求

• 求每一列的水，我们只需要关注当前列，以及左边最高的墙，右边最高的墙就够了。
• 装水的多少，当然根据木桶效应，我们只需要看左边最高的墙和右边最高的墙中较矮的一个就够了。

所以，根据较矮的那个墙和当前列的墙的高度可以分为三种情况。

1. 较矮的墙的高度大于当前列的墙的高度

把正在求的列左边最高的墙和右边最高的墙确定后，然后为了方便理解，我们把无关的墙去掉。

这样就很清楚了，现在想象一下，往两边最高的墙之间注水。正在求的列会有多少水？

很明显，较矮的一边，也就是左边的墙的高度，减去当前列的高度就可以了，也就是 2 - 1 = 1，可以存一个单位的水。

2. 较矮的墙的高度小于当前列的墙的高度

同样的，我们把其他无关的列去掉。

想象下，往两边最高的墙之间注水。正在求的列会有多少水？

正在求的列不会有水，因为它大于了两边较矮的墙。

3. 较矮的墙的高度等于当前列的墙的高度。

和上一种情况是一样的，不会有水。

程序就很好写了，遍历每一列，然后分别求出这一列两边最高的墙。找出较矮的一端，和当前列的高度比较，结果就是上边的三种情况。

class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
sum_ = 0
#最两端的列不用考虑，因为一定不会有水。所以下标从 1 到 length - 2
for i in range(1, n - 1):
max_left = 0
#找出左边最高
for j in range(i - 1, -1, -1):
if (height[j] > max_left):
max_left = height[j]
max_right = 0
#找出右边最高
for j in range(i + 1, n):
if (height[j] > max_right):
max_right = height[j]
#找出两端较小的
min_h = min(max_left, max_right);
#只有较小的一段大于当前列的高度才会有水，其他情况不会有水
if (min_h > height[i]):
sum_ = sum_ + (min_h - height[i])

return

• 时间复杂度：，遍历每一列需要 n，找出左边最高和右边最高的墙加起来刚好又是一个 n，所以是。
• 空间复杂度：。

2.2 动态规划（对法一优化）

注意到，解法一中。对于每一列，我们求它左边最高的墙和右边最高的墙，都是重新遍历一遍所有高度，这里我们可以优化一下。

首先用两个数组，​​max_left [i]​​​ 代表第 ​​i​​​ 列左边最高的墙的高度，​​max_right[i]​​​ 代表第 ​​i​​ 列右边最高的墙的高度。（一定要注意下，第 i 列左（右）边最高的墙，是不包括自身的，和 leetcode 上边的讲的有些不同）

• 对于​​max_left​​我们其实可以这样求。
  ​​max_left [i] = Max(max_left [i-1],height[i-1])​​。它前边的墙的左边的最高高度和它前边的墙的高度选一个较大的，就是当前列左边最高的墙了。
• 对于​​max_right​​我们可以这样求。
  ​​max_right[i] = Max(max_right[i+1],height[i+1])​​ 。它后边的墙的右边的最高高度和它后边的墙的高度选一个较大的，就是当前列右边最高的墙了。

这样，我们再利用解法一的算法，就不用在 ​​for​​​ 循环里每次重新遍历一次求 ​​max_left​​​ 和 ​​max_right​​ 了。

class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
sum_ = 0
max_left = [0] * n
max_right = [0] * n
for i in range(1, n - 1):
max_left[i] =max(max_left[i - 1], height[i - 1])
for i in range(n - 2, -1, -1):
max_right[i] = max(max_right[i + 1], height[i + 1])
for i in range(1, n - 1):
min_ = min(max_left[i], max_right[i])
if (min_ > height[i]):
sum_ = sum_ + (min_ - height[i])

return

• 时间复杂度：O(n)。
• 空间复杂度：O(n)，用来保存每一列左边最高的墙和右边最高的墙。

2.3 双指针（对法二再优化）

动态规划中，我们常常可以对空间复杂度进行进一步的优化。

例如这道题中，可以看到，​​max_left [ i ]​​​ 和 ​​max_right [ i ]​​ 数组中的元素我们其实只用一次，然后就再也不会用到了。所以我们可以不用数组，只用一个元素就行了。

这里要用到两个指针，​​left​​​ 和 ​​right​​，从两个方向去遍历。

left_max：左边的最大值，它是从左往右遍历找到的
right_max：右边的最大值，它是从右往左遍历找到的
left：从左往右处理的当前下标
right：从右往左处理的当前下标

• 定理一：在某个位置​​i​​处，它能存的水，取决于它左右两边的最大值中较小的一个。
• 定理二：当我们从左往右处理到​​left​​​下标时，左边的最大值​​left_max​​​对它而言是可信的，但​​right_max​​​对它而言是不可信的。（见下图，由于中间状况未知，对于​​left​​​下标而言，​​right_max​​未必就是它右边最大的值）
• 定理三：当我们从右往左处理到​​right​​​下标时，右边的最大值​​right_max​​​对它而言是可信的，但​​left_max​​对它而言是不可信的。

right_max
left_max __
__ | |
| |__ __?????????????????????? | |
__| |__| __| |__
left right

对于位置​​left​​​而言，它左边最大值一定是​​left_max​​​，右边最大值“大于等于”​​right_max​​，

这时候，如果 ​​left_max<right_max​​​ 成立，那么它就知道自己能存多少水了。无论右边将来会不会出现更大的 ​​right_max​​，都不影响这个结果。

所以当​​left_max<right_max​​​时，我们就希望去处理​​left​​​下标，反之，我们希望去处理​​right​​下标。

class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
sum_ = 0
max_left = 0
max_right = 0
left = 1
right = n - 2 # 加右指针进去
for i in range(1, n - 1):
#从左到右更
if (height[left - 1] < height[right + 1]):
max_left = max(max_left, height[left - 1])
min_ = max_left
if (min_ > height[left]):
sum_ = sum_ + (min_ - height[left])
left += 1
#从右到左更
else:
max_right = max(max_right, height[right + 1])
min_ = max_right
if (min_ > height[right]):
sum_ = sum_ + (min_ - height[right])
right -= 1

return

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

2.4 栈

说到栈，我们肯定会想到括号匹配了。我们仔细观察蓝色的部分，可以和括号匹配类比下。每次匹配出一对括号（找到对应的一堵墙），就计算这两堵墙中的水。

我们用栈保存每堵墙。

当遍历墙的高度的时候，如果当前高度小于栈顶的墙高度，说明这里会有积水，我们将墙的高度的下标入栈。

如果当前高度大于栈顶的墙的高度，说明之前的积水到这里停下，我们可以计算下有多少积水了。计算完，就把当前的墙继续入栈，作为新的积水的墙。

总体的原则就是，

当前高度小于等于栈顶高度，入栈，指针后移。

当前高度大于栈顶高度，出栈，计算出当前墙和栈顶的墙之间水的多少，然后计算当前的高度和新栈的高度的关系，重复第 2 步。直到当前墙的高度不大于栈顶高度或者栈空，然后把当前墙入栈，指针后移。

class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
if n < 3:
return 0
res = 0
cur = 0
stack = []
while cur < n:
# 如果栈不空并且当前指向的高度大于栈顶高度就一直循环
while len(stack) > 0 and height[cur] > height[stack[-1]]:
top = stack.pop() # index of the last element in the stack, 取出要出栈的元素
if len(stack) == 0: # 栈空就出去
break
dist = cur - stack[-1] - 1 # 两堵墙之前的距离。
min_ = min(height[stack[-1]], height[cur])
res = res + dist * (min_ - height[top])
stack.append(cur)
cur += 1
return

• 时间复杂度：O(n)。虽然 while 循环里套了一个 while 循环，但是考虑到每个元素最多访问两次，入栈一次和出栈一次，所以时间复杂度是 O(n)。
• 空间复杂度：O(n)。栈的空间。

参考：

​​LeetCode题解​​

​​LeetCode官方题解 & 评论区​​