小旭讲解 LeetCode 407. Trapping Rain Water II

BiliBili

YouTube

原题

中文

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

说明

m 和 n 都是小于110的整数。每一个单位的高度都大于 0 且小于 20000。

英文

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.

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.

After the rain, water is trapped between the blocks. The total volume of water trapped is 4.

思路

代码

struct Node{
    int r;
    int c;
    int h;
    Node(int row, int col, int height) : r(row), c(col), h(height) {};
    bool operator>(Node a) const {return h > a.h;};
};
class Solution {
public:
    int trapRainWater(vector<vector<int>>& hm) {
        int r = 0, c = 0;
        if ((r = hm.size()) == 0 || (c = hm[0].size()) == 0) return 0;
        vector<vector<int>> vis(r, vector<int>(c, 0));
        priority_queue<Node, vector<Node>, greater<Node> > pq;
        
        for (int i = 0; i < c; ++i) {
            pq.push(Node(0, i, hm[0][i]));
            pq.push(Node(r - 1, i, hm[r - 1][i]));
            vis[0][i] = 1;
            vis[r - 1][i] = 1;
        }
        
        for (int i = 1; i < r - 1; ++i) {
            pq.push(Node(i, 0, hm[i][0]));
            pq.push(Node(i, c - 1, hm[i][c - 1]));
            vis[i][0] = 1;
            vis[i][c - 1] = 1;
        }
        
        int water = 0, vis_max = INT_MIN;
        vector<int> d{0, -1, 0, 1, 0};
        
        while (!pq.empty()) {
            auto node = pq.top();
            pq.pop();
            
            water += (vis_max > node.h) ? vis_max - node.h : 0;
            vis_max = max(vis_max, node.h);
            
            for (int di = 0; di < 4; ++di) {
                int nr = node.r + d[di];
                int nc = node.c + d[di + 1];
                if (nr < 0 || nr >= r || nc < 0 || nc >= c) continue;
                if (vis[nr][nc] == 1) continue;
                
                vis[nr][nc] = 1;
                pq.push(Node(nr, nc, hm[nr][nc]));
            }
        }
        
        return water;
    }
};

复杂度分析

时间复杂度：O(n \log n) n = m * n
空间复杂度：O(n)

参考

原题链接：https://leetcode.com/problems/trapping-rain-water-ii/

欢迎分享，引用。若转载，请联系我，谢谢配合。
本文地址：https://qoogle.top/leetcode-407-trapping-rain-water-ii/