既然智商到了瓶颈,那就继续开始翻译事业吧。
这是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