[LeetCode] Trapping Rain Water II 收集雨水之二

墨蓝 2022-03-27 05:46 81阅读 0赞

Given an `m x n` matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.

**Note:**  
Both *m* and *n* are less than 110. The height of each unit cell is greater than 0 and is less than 20,000.

**Example:**

Given the following 3x6 height map:
    [
      [1,4,3,1,3,2],
      [3,2,1,3,2,4],
      [2,3,3,2,3,1]
    ]
    
    Return 4.

![rainwater_empty.png][]  
The above image represents the elevation map `[[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]` before the rain.

![rainwater_fill.png][]  
After the rain, water are trapped between the blocks. The total volume of water trapped is 4.

这道题是之前那道[Trapping Rain Water][]的拓展，由2D变3D了，感觉很叼。但其实解法跟之前的完全不同了，之前那道题由于是二维的，我们可以用双指针来做，而这道三维的，我们需要用BFS来做，解法思路很巧妙，下面我们就以题目中的例子来进行分析讲解，多图预警，手机流量党慎入：

首先我们应该能分析出，能装水的底面肯定不能在边界上，因为边界上的点无法封闭，那么所有边界上的点都可以加入queue，当作BFS的启动点，同时我们需要一个二维数组来标记访问过的点，访问过的点我们用红色来表示，那么如下图所示：

![391947-20161003120051785-2137527353.jpg][]

我们再想想，怎么样可以成功的装进去水呢，是不是周围的高度都应该比当前的高度高，形成一个凹槽才能装水，而且装水量取决于周围最小的那个高度，有点像木桶原理的感觉，那么为了模拟这种方法，我们采用模拟海平面上升的方法来做，我们维护一个海平面高度mx，初始化为最小值，从1开始往上升，那么我们BFS遍历的时候就需要从高度最小的格子开始遍历，那么我们的queue就不能使用普通队列了，而是使用优先级队列，将高度小的放在队首，最先取出，这样我们就可以遍历高度为1的三个格子，用绿色标记出来了，如下图所示：

![391947-20161003120900692-314831597.jpg][]

如上图所示，向周围BFS搜索的条件是不能越界，且周围格子未被访问，那么可以看出上面的第一个和最后一个绿格子无法进一步搜索，只有第一行中间那个绿格子可以搜索，其周围有一个灰格子未被访问过，将其加入优先队列queue中，然后标记为红色，如下图所示：

![391947-20161003121601785-791353712.jpg][]

那么优先队列queue中高度为1的格子遍历完了，此时海平面上升1，变为2，此时我们遍历优先队列queue中高度为2的格子，有3个，如下图绿色标记所示：

![391947-20161003121753379-2129390635.jpg][]

我们发现这三个绿格子周围的格子均已被访问过了，所以不做任何操作，海平面继续上升，变为4，遍历所有高度为4的格子，如下图绿色标记所示：

![391947-20161003121905207-4147516.jpg][]

由于我们没有特别声明高度相同的格子在优先队列queue中的顺序，所以应该是随机的，其实谁先遍历到都一样，对结果没啥影响，我们就假设第一行的两个绿格子先遍历到，那么那么周围各有一个灰格子可以遍历，这两个灰格子比海平面低了，可以存水了，把存水量算出来加入结果res中，如下图所示：

![391947-20161003122502614-299103818.jpg][]

上图中这两个遍历到的蓝格子会被加入优先队列queue中，由于它们的高度小，所以下一次从优先队列queue中取格子时，它们会被优先遍历到，那么左边的那个蓝格子进行BFS搜索，就会遍历到其左边的那个灰格子，由于其高度小于海平面，也可以存水，将存水量算出来加入结果res中，如下图所示：

![391947-20161003122735129-1777610725.jpg][]

等两个绿格子遍历结束了，它们会被标记为红色，蓝格子遍历会先被标记红色，然后加入优先队列queue中，由于其周围格子全变成红色了，所有不会有任何操作，如下图所示：

![391947-20161003122909770-1492433975.jpg][]

此时所有的格子都标记为红色了，海平面继续上升，继续遍历完优先队列queue中的格子，不过已经不会对结果有任何影响了，因为所有的格子都已经访问过了，此时等循环结束后返回res即可，参见代码如下：

class Solution {
    public:
        int trapRainWater(vector<vector<int>>& heightMap) {
            if (heightMap.empty()) return 0;
            int m = heightMap.size(), n = heightMap[0].size(), res = 0, mx = INT_MIN;
            priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
            vector<vector<bool>> visited(m, vector<bool>(n, false));
            vector<vector<int>> dir{
        {
        0,-1},{-1,0},{
        0,1},{
        1,0}};
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                        q.push({heightMap[i][j], i * n + j});
                        visited[i][j] = true;
                    }
                }
            }
            while (!q.empty()) {
                auto t = q.top(); q.pop();
                int h = t.first, r = t.second / n, c = t.second % n;
                mx = max(mx, h);
                for (int i = 0; i < dir.size(); ++i) {
                    int x = r + dir[i][0], y = c + dir[i][1];
                    if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y]) continue;
                    visited[x][y] = true;
                    if (heightMap[x][y] < mx) res += mx - heightMap[x][y];
                    q.push({heightMap[x][y], x * n + y});
                }
            }
            return res;
        }
    };

类似题目：

[Trapping Rain Water][]

参考资料：

[https://discuss.leetcode.com/topic/60914/concise-c-priority\_queue-solution][https_discuss.leetcode.com_topic_60914_concise-c-priority_queue-solution]

[LeetCode All in One 题目讲解汇总(持续更新中...)][LeetCode All in One _...]

[rainwater_empty.png]: https://leetcode.com/static/images/problemset/rainwater_empty.png
[rainwater_fill.png]: https://leetcode.com/static/images/problemset/rainwater_fill.png
[Trapping Rain Water]: http://www.cnblogs.com/grandyang/p/4402392.html
[391947-20161003120051785-2137527353.jpg]: /images/20220327/74a1689ff3d04ddebd2282acb532f1af.png
[391947-20161003120900692-314831597.jpg]: /images/20220327/1157e9073503406bad8b4d073da1958c.png
[391947-20161003121601785-791353712.jpg]: /images/20220327/ba1ff90ca3fa4c14b04442e22692251a.png
[391947-20161003121753379-2129390635.jpg]: /images/20220327/18305457dbaf4860823d7d8c39b7f4f6.png
[391947-20161003121905207-4147516.jpg]: /images/20220327/4518ec84d2e14ecb86e12fb3c957b652.png
[391947-20161003122502614-299103818.jpg]: /images/20220327/af2176fa1c7149828535e5e4b65b9f04.png
[391947-20161003122735129-1777610725.jpg]: /images/20220327/3fb2391eb4c948a7a16dd62226e4795e.png
[391947-20161003122909770-1492433975.jpg]: /images/20220327/22c4cfb8d97c40a6868d552c8eefc8bd.png
[https_discuss.leetcode.com_topic_60914_concise-c-priority_queue-solution]: https://discuss.leetcode.com/topic/60914/concise-c-priority_queue-solution
[LeetCode All in One _...]: http://www.cnblogs.com/grandyang/p/4606334.html