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

[ltd (Lê Trần Đạt)]

Đề bài

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

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ẻ

[japananh (Trần Nhật Anh)]

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.