407.接雨水II.md

407.接雨水II

https://leetcode-cn.com/problems/trapping-rain-water-ii/

错误解

直接照抄42.接雨水的解法一，把一维方法照搬到二维来，对每个位置（i，j）找左右的最高点a、b和上下的最高点c、d，然后取abcd中最小值就是（i，j）处能接到的最多雨水

class Solution:
    def trapRainWater(self, heightMap) -> int:
        m = len(heightMap)
        n = len(heightMap[0])
        if m < 2:
            return  0
        res = 0
        for i in range(1, m-1):
            for j in range(1, n-1):
                # 找左右的最高点
                a,b = 0, 0
                for x in range(i-1, -1, -1):
                    a = max(a, heightMap[x][j])
                for x in range(i+1, m):
                    b = max(b, heightMap[x][j])
                c,d = 0,0
                for y in range(j-1, -1, -1):
                    c = max(c, heightMap[i][y])
                for y in range(j+1, n):
                    d = max(d, heightMap[i][y])
                height = min(a,b,c,d)
                if height > heightMap[i][j]:    #周围比(i,j)高才能接到水
                    res += (height-heightMap[i][j])
        return res

这种方法的错误在于没有考虑二维上的连通性，例如第二列4、8，按上面的方法这两个位置水位最多能到13，然而8右边还有10，他们是连通的（加粗的三个元素），因此这三个位置水位最多只能到12

12 13 1 12

13 4 13 12

13 8 10 12

12 13 12 12

13 13 13 13

正确解

模拟“水往低处走”的性质，从最低的元素入手

从边缘开始，所有元素入堆，每次弹出一个最小的元素（利用堆 的性质）。对每个弹出的元素（i，j），访问其上下左右位置，若小于当前位置，说明能存储水，且水位最高为heightMap[i][j]，用全局变量累加。

重复以上操作，直至堆空

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        if len(heightMap) < 2 or len(heightMap[0]) < 2:
            return 0

        m, n = len(heightMap), len(heightMap[0])
        visited = [[0 for _ in range(n)] for _ in range(m)]
        pq = []
        for i in range(m):	#边缘全部入堆
            for j in range(n):
                if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                    # 避免重复访问
                    visited[i][j] = 1
                    # 以元组（高度、坐标）入堆
                    heapq.heappush(pq, (heightMap[i][j], i * n + j))
        
        res = 0
        dirs = [-1, 0, 1, 0, -1]	#辅助数组，在下文4次循环中，巧妙实现访问上下左右四个方向
        while pq:
          	#分别从堆中取出高度和坐标
            height, position = heapq.heappop(pq)
            for k in range(4):
              	#坐标转换为二维
                nx, ny = position // n + dirs[k], position % n + dirs[k + 1]
                if nx >= 0 and nx < m and ny >= 0 and ny < n and visited[nx][ny] == 0:
                    if height > heightMap[nx][ny]:
                        res += height - heightMap[nx][ny]
                    visited[nx][ny] = 1    
                    heapq.heappush(pq, (max(height, heightMap[nx][ny]), nx * n + ny))
        return res