python solution with heap


  • 12
    S
    class Solution(object):
        def trapRainWater(self, heightMap):
            if not heightMap or not heightMap[0]:
                return 0
            
            import heapq    
            m, n = len(heightMap), len(heightMap[0])
            heap = []
            visited = [[0]*n for _ in xrange(m)]
    
            # Push all the block on the border into heap
            for i in xrange(m):
                for j in xrange(n):
                    if i == 0 or j == 0 or i == m-1 or j == n-1:
                        heapq.heappush(heap, (heightMap[i][j], i, j))
                        visited[i][j] = 1
            
            result = 0
            while heap:
                height, i, j = heapq.heappop(heap)    
                for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
                    if 0 <= x < m and 0 <= y < n and not visited[x][y]:
                        result += max(0, height-heightMap[x][y])
                        heapq.heappush(heap, (max(heightMap[x][y], height), x, y))
                        visited[x][y] = 1
            return result
    

    The idea is that we maintain all the points of the current border in a min heap and always choose the point with the lowest length. This is actually an optimized searching strategy over the trivial brute force method: instead of dfs each point to find the lowest "border" of its connected component, we can always start a search from the lowest border and update the points adjacent to it.


  • 0
    S

    so interesting a solve


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.