Leetcode 407. 接雨水 II (2025.10.03每日一题)(自翻解)

既然智商到了瓶颈,那就继续开始翻译事业吧。
这是2025年10月3日Leetcode.cn的每日一题。
407. 接雨水 II
如下是灵茶山艾府大神的Python解

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        m, n = len(heightMap), len(heightMap[0])
        h = []
        for i, row in enumerate(heightMap):
            for j, height in enumerate(row):
                if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                    h.append((height, i, j))
                    row[j] = -1  # 标记 (i,j) 访问过
        heapify(h)

        ans = 0
        while h:
            min_height, i, j = heappop(h)  # min_height 是木桶的短板
            for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):
                if 0 <= x < m and 0 <= y < n and heightMap[x][y] >= 0:  # (x,y) 没有访问过
                    # 如果 (x,y) 的高度小于 min_height,那么接水量为 min_height - heightMap[x][y]
                    ans += max(min_height - heightMap[x][y], 0)
                    # 给木桶新增一块高为 max(min_height, heightMap[x][y]) 的木板
                    heappush(h, (max(min_height, heightMap[x][y]), x, y))
                    heightMap[x][y] = -1  # 标记 (x,y) 访问过
        return ans

如下是我按照Python原意,逐句翻译的Ruby解,又用到了Algorithm gem,开心。但不是Ruby官方缩进风格,不喜勿喷。

# @param {Integer[][]} height_map
# @return {Integer}
def trap_rain_water(height_map)
    m,n = height_map.length,height_map[0].length
    h = []
    height_map.each_with_index do |row,i|
        row.each_with_index do |height,j|
            if i == 0 || i == m - 1 || j == 0 || j == n - 1
                h.push([height,i,j])
                row[j] = -1
            end
        end
    end
    h = Containers::MinHeap.new(h)
    ans = 0
    while h.size > 0
        min_height,i,j = h.pop
        for (x,y) in [[i,j-1],[i,j+1],[i-1,j],[i+1,j]]
            if x >= 0 && x < m && y >= 0 && y < n && height_map[x][y] >= 0
                ans += [min_height-height_map[x][y],0].max
                h.push([[min_height,height_map[x][y]].max,x,y])
                height_map[x][y] = -1
            end
        end
    end
    ans
end
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容