小旭讲解 LeetCode 407. Trapping Rain Water II
小旭讲解 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.

思路

小旭讲解 LeetCode 407. Trapping Rain Water II
小旭讲解 LeetCode 407. Trapping Rain Water II

代码

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/
最后修改日期:2020年6月18日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。