8.21 - hard - 79

407. Trapping Rain Water II

利用外围边界，依次朝里面找，只是新加入heap的值需要取其原来值和新值比较高的那个点作为高度。

class Solution(object):
    def trapRainWater(self, heightMap):
        """
        :type heightMap: List[List[int]]
        :rtype: int
        """
        if not heightMap:
            return 0
        # 利用heap来做
        visited = [[False for _ in range(len(heightMap[0]))] for _ in range(len(heightMap))]
        
        # init
        heap = []
        for i in range(len(heightMap)):
            for j in range(len(heightMap[0])):
                if i == 0 or i == len(heightMap) - 1 or j == 0 or j == len(heightMap[0]) - 1:
                    heapq.heappush(heap, [heightMap[i][j], i, j])
                    visited[i][j] = True
        
        # find the lowest one
        res = 0
        while heap:
            cur, i, j = heapq.heappop(heap)
            for x, y in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:
                if 0 <= x < len(heightMap) and 0 <= y < len(heightMap[0]) and not visited[x][y]:
                    res += max(0, cur - heightMap[x][y])
                    heapq.heappush(heap, [max(cur, heightMap[x][y]), x, y])
                    visited[x][y] = True
        
        return res