leetcode 接雨水II(407)

题目:

给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。

示例 1:

输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
输出: 4
解释: 下雨后，雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=4。

示例 2:

输入: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
输出: 10

提示:

• m == heightMap.length
• n == heightMap[i].length
• 1 <= m, n <= 200
• 0 <= heightMap[i][j] <= 2 * 104

解题思路:

通过"木桶原理”：
水位由最短的板子决定。我们可以从矩阵的边界开始，逐渐向内推进，确保每次遇到的都是当前最低的高度，从而确定可以存储的水量

解决方式:

使用优先队列（最小堆）来解决

import heapq

class Solution(object):
    def trapRainWater(self,heightMap):
        if not heightMap or not heightMap[0]:
            return 0

        m, n = len(heightMap), len(heightMap[0])
        if m < 3 or n < 3:
            return 0

        # 初始化最小堆和访问标记
        heap = []
        visited = [[False] * n for _ in range(m)]

        # 将最外层的所有元素加入堆，并标记为已访问
        for i in range(m):
            heapq.heappush(heap, (heightMap[i][0], i, 0))
            heapq.heappush(heap, (heightMap[i][n-1], i, n-1))
            visited[i][0] = visited[i][n-1] = True
        for j in range(1, n-1):
            heapq.heappush(heap, (heightMap[0][j], 0, j))
            heapq.heappush(heap, (heightMap[m-1][j], m-1, j))
            visited[0][j] = visited[m-1][j] = True

        # 方向数组，用于遍历四个方向
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        water_trapped = 0
        max_height = 0

        while heap:
            height, x, y = heapq.heappop(heap)
            max_height = max(max_height, height)

            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
                    visited[nx][ny] = True
                    next_height = heightMap[nx][ny]
                    if next_height < max_height:
                        water_trapped += max_height - next_height
                    heapq.heappush(heap, (next_height, nx, ny))

        return water_trapped

# 示例用法：
print(Solution().trapRainWater([[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]))  # 输出: 4
print(Solution().trapRainWater([[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]))  # 输出: 10