Giải bài 407 trapping rain water II O(N^2)

Đề bài

Bài giải

Code Python

class Solution(object):
    def trapRainWater(self, hm):
        """
        :type hm: List[List[int]]
        :rtype: int
        """
        if not hm or not hm[0]: return 0
        m, n = len(hm), len(hm[0])
        visit = [[0] * n for _ in xrange(m)]
        h = []
        
        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(h, (hm[i][j], i, j))
                    visit[i][j] = 1
                    
        water = 0
        while h:
            v, i, j = heapq.heappop(h)
            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 visit[x][y]:
                    water += max(0, v - hm[x][y])
                    heapq.heappush(h, (max(v, hm[x][y]), x, y))
                    visit[x][y] = 1
        return water

Nhờ các bạn giải với các ngôn ngữ khác.

Sau hôm nay mình bận công việc sẽ tạm không quay được video, sau tết sẽ sắp xếp được thời gian. Chúc ae ăn tết vui vẻ :slight_smile:

5 Likes

Em đã xem hết các videos về interview của anh. Cảm ơn anh đã chia sẻ. Hi vọng anh sẽ làm thêm nhiều video nữa.

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?