接雨水
这也是在一次字节的面试中遇到的题目，暂时也没有在 LC 找到题目的原型。题目是这样描述的：
给定一个二维矩阵，用于描述一处山地的地形，每个元素 a(i, j) 代表该座标位置的海拔高度，设想，现在下了一场足够大的雨后，将所有低洼处都填上水，请判断座标 (x,y) 的最高高度能否达到 h？（最高高度既可以是陆地，也可以是水面）举个例子：
给定地形为：1
2
3
43, 3, 3, 3
3, 1, 2, 3
3, 3, 3, 3
3, 3, 3, 3
在这个地形里，坐标（1，1）的高度是 1，坐标（1，2）的高度是 2，其余位置高度都是 3，我们假设矩阵外部全是深渊，现在低洼就是（1，1）和（1，2）两个格子。很显然，灌水后，会被填平，所有的坐标高度都将达到 3。（被水填平了）
decideHeight( x=1, y=1, h=3) 返回 True，坐标（1，1）位置能否达到高度 3？答案是 True。
decideHeight(x=1, y=2, h=4) 返回 False，坐标（1，2）位置能否达到高度 4？答案是 False。
其实，我在 LC 做过一个一维的接雨水的题目，给定的是一个截面图，然后用两侧的柱子高度来盛水，计算总共能接多少水。但是这个题目不一样，这个是判定水面的高度。受到一维题目的影响，我一直在往那个方向思考，无非就是把一维改为二维，先判断一个方向的盛水情况，再判定另一个方向。
但是我怎么也想不明白怎么做。后来面试官提示我第一点，我没必要计算出实际盛水的数量，做判断和计算具体值，是不一样的。其实这是非常重要的一个提示。因为只是做判定的话，就比具体算出来是多少要简单一点。
只考虑一个方向，两侧如果有高于给定高度的遮挡，则可以认为能够接水，否则就是不行。扩展到二维后，一个坐标点，需要四个方向来遮挡，才能盛水。所以给定一个坐标后，我们判定其四个方向，如果都高于给定坐标，则认为能接水。如果，并不高于给定坐标，那么是不是一定不行呢？未必，因为如果更远处有足够高的遮挡，也可以实现盛水。所以我们要将当前判断记为暂定，然后向远处延伸出去判定，直到找到封闭的遮挡或者触达边界。
于是，我写出了这样的算法：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
27def rainDrop(m: List[List[int]], a: int, b: int, h: int) -> bool:
row = len(m)
col = len(m[0])
visited = [[0] * col for i in range(row)]
def _rainDrop(x: int, y: int) -> bool:
visited[x][y] = 1
if m[x][y] >= h: return True
if x - 1 < 0: return False
if x + 1 >= row: return False
if y - 1 < 0: return False
if y + 1 >= col: return False
res = True
if visited[x-1][y] == 0:
res = res and _rainDrop(x - 1, y)
if visited[x+1][y] == 0:
res = res and _rainDrop(x + 1, y)
if visited[x][y-1] == 0:
res = res and _rainDrop(x, y - 1)
if visited[x][y+1] == 0:
res = res and _rainDrop(x, y + 1)
return res
return _rainDrop(a,b)
这个实现里，我用了一个递归算法，如果当前坐标的高度本身已经高于需要判定的高度，直接返回 True，否则就向四个方向延伸去判定是否能够遮挡。不过呢？为了避免重复，需要一个位图来记住已经访问过的坐标。这个算法，很显然，时空复杂度是 O(m×n)，因为最坏情况会遍历每个格子一次，需要格子同等数量的位图来记录访问历史。
其实在面试当场，我是没能写对的，我没有能防止重复遍历，回来写出来运行后，发现我当时写的版本会死循环。遗憾。
等我写对后，我发现，这题目本质上是一个无向图的广度优先遍历，和一维接雨水毫无关系的一个算法类别。还真是，类似的表述会是完全不同的算法。所以还是要深入去掌握题目的条件和问题来思考算法，不能凭记忆和感觉解题。