题目来源

• leetcode：407. 接雨水 II

题目描述

class Solution {
    
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
    

    }
};

题目解析

跟一维数组类似，我们还是只求每一个格子最多能存放多少水，然后加起来。但是这个最多能存放多少水应该怎么求呢？

优先队列+由外向内搜索

问题：哪些格子可以接到水？

• 边界一定不行
• 格子能存水的前提：有边界，而且边界的最低也比自己高

想法：

• 从边界往里面扩散
• 只有比边界低的才能存水
• 根据木桶原理：
  • 每次往里面扩散的时候要找边界中最低的高度(它是瓶颈，可以用最小堆解决)，从这个点开始往里面扩散
  • 扩散的时候找邻接节点，如果比当前边界中最低的还低，说明可以填入水。否则，该位置将成为新的边界。
• 我们让每个位置只入堆一次即可保证正确性。正确性来自于两点：
  • 我们在优先队列里维护的边界是一个完整的边界。每次会把边界的所有邻接点入队，边界不会出现空隙。
  • 边界没有空隙的前提下，判断一个位置是不是能蓄水，当然只需要判断和边界中最低的位置比较即可。
• 怎么确保一个位置只入堆一次呢？用一个vis数组就可以解决

整体思路

• 在整个过程中需要维护两个变量：water(总水量)、max(瓶颈)
  • 初始时max = 0， water为0
  • 首次围圈：取最外围柱子就得到一圈木桶，并入堆
  • 找圈上最矮柱子：即找木桶最短板，堆顶出堆并更新max(弹出的元素就是新的瓶颈)
  • 针对圈上最矮柱子的相邻圈内柱子，尝试灌水进去（结算water）
    • 根据木桶原理，能否灌水进去，取决于圈上木桶最短板（即圈上最矮柱子）、桶底（即相邻圈内柱子）的高度
    • 如果相邻圈内柱子低于圈上最矮柱子，就能灌水且水流不出圈，最多可灌水至高度等于圈上最矮柱子
  • 缩圈：相邻圈内柱子入堆（如果可灌水，高度为灌水后的高度）

其实和一维接雨水最简思路本质一回事。都是从最外层往里蚕食，每次从最外层找一个最低的，然后蚕食跟它相邻的。只是一维数组最外层就俩，用max就能分辨，各自相邻的也就一个。而二维数组最外层一圈所以需要用优先队列，相邻4个方向要各自试探

手动动画在这里

class Solution {
    
    struct Node{
    
        int value;
        int row;
        int col;

        Node(int v, int i, int j) {
    
            value = v;
            row = i;
            col = j;
        }

        bool operator> (const Node &other) const {
    
            return this->value > other.value;
        }
    };
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
    
        if(heightMap.empty() || heightMap[0].empty()){
    
            return 0;
        }
        
        int N = heightMap.size(), M = heightMap[0].size();
        std::vector<std::vector<bool>> isEnter(N, std::vector<bool>(M));
        std::priority_queue<Node, std::vector<Node>, std::greater<Node>> minHeap;
        for (int j = 0; j < M - 1; ++j) {
      // 0 1 2 3 4 M - 2
            isEnter[0][j] = true;
            minHeap.push(Node(heightMap[0][j], 0, j));
        }
        for (int i = 0; i < N - 1; ++i) {
      // 0:M - 1
            isEnter[i][M - 1] = true;      // 1:M - 1
            minHeap.push(Node(heightMap[i][M - 1], i, M - 1)); // N-2 : M -1
        }
        for (int j = M - 1; j > 0; --j) {
    
            isEnter[N - 1][j] = true;
            minHeap.push(Node(heightMap[N - 1][j], N - 1, j));
        }
        for (int i = N - 1; i > 0; --i) {
    
            isEnter[i][0] = true;
            minHeap.push(Node(heightMap[i][0], i, 0));
        }
        
        int water = 0, max = 0;
        while (!minHeap.empty()){
    
            auto cur = minHeap.top(); minHeap.pop();
            max = std::max(max, cur.value);
            int r = cur.row;
            int c = cur.col;
            if (r > 0 && !isEnter[r - 1][c]) {
    
                water += std::max(0, max - heightMap[r - 1][c]);
                isEnter[r - 1][c] = true;
                minHeap.push( Node(heightMap[r - 1][c], r - 1, c));
            }
            if (r < N - 1 && !isEnter[r + 1][c]) {
    
                water += std::max(0, max - heightMap[r + 1][c]);
                isEnter[r + 1][c] = true;
                minHeap.push( Node(heightMap[r + 1][c], r + 1, c));
            }
            if (c > 0 && !isEnter[r][c - 1]) {
    
                water += std::max(0, max - heightMap[r][c - 1]);
                isEnter[r][c - 1] = true;
                minHeap.push( Node(heightMap[r][c - 1], r, c - 1));
            }
            if (c < M - 1 && !isEnter[r][c + 1]) {
    
                water += std::max(0, max - heightMap[r][c + 1]);
                isEnter[r][c + 1] = true;
                minHeap.push( Node(heightMap[r][c + 1], r, c + 1));
            }
        }
        
        return water;
    }
};

并查集

为什么可以用并查集

从低到高枚举水面的高度，用并查集合并相邻的“水池”，并维护总体积。

题目问的是，各个单元能容纳水的最大数量，考虑先对所有单元按照高度升序排列，然后模拟涨水过程，每次将水位涨到未处理单元的最小高度。

每次处理一个单元格时，如果其上下使用方向存在其他已经处理的单元，将它们并入同一个集合中，如果并入集合后，该集合与边界连通

说明蓝色单元集合最大盛水高度即为当前水位高度（也即橘色单元的高度），将蓝色单元集合并入绿色单元集合，并将蓝色单元集合的盛水量加入入最终结果

因为是按照高度从小到大的顺序处理，故蓝色单元集合周围的其它单元的高度必然大于等于橘色单元的高度

我的疑问（待实践）

是leetcode：42. 接雨水的扩展

• 1-D的接雨水问题有一种解法是从左右两边的边界往中间不断进行收缩，收缩的过程中，对每个坐标（一维坐标）能接的雨水进行求解
• 能不能将二维转为一维，然后用一维接雨水的方法来解决此题目?

• 本题是一道立体图，对于 heightMap上索引为 (x, y)的点，我们不能单纯的考虑$min((x,y)分别在四个方向上的最大值))$，这里给大家举个例子便一目了然：
  
• 对于图中高度为 4 的点，虽然在四个方向上最大的值都是 13，但是其实水的高度是只能达到 12（斜着的边）的，由此可见，这道题考虑的不仅仅是四个方向，而是整个平面。

二维改一维待补充（证明其不行）