题目

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

示例 1：
[困难] 407. 接雨水 II - 图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：
[困难] 407. 接雨水 II - 图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

解答 & 代码

优先队列（小根堆）

官方题解 - 接雨水 Ⅱ 优先队列的思路解决接雨水II，逐行解释

核心思想：先确定木桶的外围，找到外围高度最低的木板，以这个高度对其周围四个格子储水，并更新木桶外围（收缩）

[困难] 42. 接雨水中，因为是二维的，因此我们维护了左、右两个最高的木板高度，根据木桶原理，对每一格，取两者中较小的木板高度作为该格能储水的高度。
而本题是三维的，因此需要维护前、后、左、右四个外围方向的最高木板高度，对于每一格，取四者中较小的木板高度作为该格能储水的高度。

因此，

初始将矩阵的四个边界作为外围木板

将四个边界的每一格的高度都存储到优先队列（小根堆），来维护木桶当前的外围木板的最小值

收缩外围边界：
1. 每次取当前外围边界木板高度的最小值（弹出小根堆对顶），设高度为 height
2. 访问其前、后、左、右四个格子，对于这四个格子的每一格，如果未被访问过（如果已访问过说明已经是边界了）：（用 visited 数组维护每个格子是否被访问过）
  1. 标记该格为已访问
  2. height 就是该格能储水的最大高度
  3. max(0, height - 该格高度) 就是该格的储水量。该格高度可能大于 height，就无法储水
  4. 该格成为新的边界，将 max(height, 该格高度）存储到小根堆，作为该边界位置的高度

struct UNIT {        /* 单元格 */
    int row;        // 行号
    int col;        // 列号
    int height;        // 高度
};

struct cmp {
    bool operator() (UNIT u1, UNIT u2) {
        return u1.height > u2.height;
    }
};

class Solution {
public:
    /* 先确定木桶的外围，找到外围高度最低的木板，以这个高度对其周围四个格子储水，并更新木桶外围（收缩）*/
    int trapRainWater(vector<vector<int>>& heightMap) {
        int totalCap = 0;
        if(heightMap.size() <= 2 || heightMap[0].size() <= 2)        // 特殊情况：行数 or 列数小于等于 2 不能接雨水
            return totalCap;

        int rows = heightMap.size();
        int cols = heightMap[0].size();
        priority_queue<UNIT, vector<UNIT>, cmp> minHeap;                 // 优先队列（小根堆）
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));    // 访问数组

        // 1. 初始将矩阵的四个边界作为外围木板
        for(int col = 0; col < cols; ++col)
        {
            minHeap.push(UNIT{0, col, heightMap[0][col]});    // 将每一格的高度存储到优先队列
            visited[0][col] = true;                            // 标记为已访问（已经是边界）
            minHeap.push(UNIT{rows - 1, col, heightMap[rows - 1][col]});
            visited[rows - 1][col] = true;
        }
        for(int row = 1; row < rows - 1; ++row)
        {
            minHeap.push(UNIT{row, 0, heightMap[row][0]});
            visited[row][0] = true;
            minHeap.push(UNIT{row, cols - 1, heightMap[row][cols - 1]});
            visited[row][cols - 1] = true;
        }

        vector<int> directions = {-1, 0, 1, 0, -1};
        // 2. 收缩外围边界
        while(!minHeap.empty())
        {
            UNIT minEdge = minHeap.top();                    // 当前外围边界木板高度的最小值
            minHeap.pop();
            for(int i = 0; i < 4; ++i)                        // 访问其前、后、左、右四个格子
            {
                int neighborRow = minEdge.row + directions[i];
                int neighborCol = minEdge.col + directions[i + 1];
                if(neighborRow >= 0 && neighborRow < rows &&
                    neighborCol >= 0 && neighborCol < cols && 
                    visited[neighborRow][neighborCol] == false)
                {
                    visited[neighborRow][neighborCol] = true;                                        // 标记该格为已访问
                    int cap = max(0, minEdge.height - heightMap[neighborRow][neighborCol]);            // 该格的储水量
                    totalCap += cap;                                                                // 加到总容量上
                    UNIT neighborUnit = {neighborRow, 
                                        neighborCol, 
                                        max(minEdge.height, heightMap[neighborRow][neighborCol])};    // 该格成为新的边界，其作为边界的高度
                    minHeap.push(neighborUnit);                                                        // 将该高度存入小根堆
                }
            }
        }

        return totalCap;
    }
};

复杂度分析：设矩阵 m 行 n 列

时间复杂度 O(mn log(m + n))：每一格都会插入优先队列一次，每次插入的时间复杂度为 O(log(m + n))
空间复杂度 O(mn)：

执行结果：

执行结果：通过

执行用时：76 ms, 在所有 C++ 提交中击败了 27.45% 的用户
内存消耗：14.1 MB, 在所有 C++ 提交中击败了 37.95% 的用户