lc-407-trapping-rain-water-ii.org

LC 407. Trapping Rain Water II

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

其实这道题目我还没有总结好，但是隐隐地觉得有些模式在里面，就是如何将一个二维区域收缩起来。

大致思路就是：

1. 现将外围的高度加入到PriorityQueue里面
2. 不断地找到最小高度点(h, x, y), 因为我们已经将外围高度全部包含进来了，所以肯定能围到h高度。
3. 观察(x,y)附近的点，如果有点(x2, y2)高度是h2<h的话，那么先将它填满到h高度
4. 将(x2, y2)加入到PQ里面，但是以max(h, h2)的高度加入，这是因为如果h2<h的话，我们已经将它填满到了h高度。

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        n, m = len(heightMap), len(heightMap[0])
        visited = set()
        hp = []
        for i in range(n):
            hp.append((heightMap[i][0], i, 0))
            hp.append((heightMap[i][m - 1], i, m - 1))
            visited.add((i, 0))
            visited.add((i, m - 1))
        for i in range(m):
            hp.append((heightMap[0][i], 0, i))
            hp.append((heightMap[-1][i], n - 1, i))
            visited.add((0, i))
            visited.add((n - 1, i))

        import heapq
        heapq.heapify(hp)

        ans = 0
        while hp:
            (h, x, y) = heapq.heappop(hp)
            for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                x2, y2 = x + dx, y + dy
                if 0 <= x2 < n and 0 <= y2 < m and (x2, y2) not in visited:
                    visited.add((x2, y2))
                    h2 = heightMap[x2][y2]
                    if h > h2:
                        ans += (h - h2)
                    heapq.heappush(hp, (max(h2, h), x2, y2))
        return ans