力扣-接雨水2

1.问题描述

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

示例：

给出如下 3x6 的高度图:

[

  [1,4,3,1,3,2],

  [3,2,1,3,2,4],

  [2,3,3,2,3,1]

]

返回 4 。

如下图所示，这是下雨前的高度图[[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] 的状态。

下雨后，雨水将会被存储在这些方块中。总的接雨水量是4。

说明：

• 1 <= m, n <= 110

• 0 <= heightMap[i][j] <= 20000

2.输入说明

首先输入高度图的行列数m和n

然后输入m行，每行n个非负整数，表示heightMap的元素值，以空格分隔。

• 1 <= m, n <= 110

• 0 <= heightMap[i][j] <= 20000

3.输出说明

输出一个整数，表示结果。

4.范例

输入：

3 6
1 4 3 1 3 2
3 2 1 3 2 4
2 3 3 2 3 1

输出：

4

5.思路

代码链接：https://leetcode.cn/problems/trapping-rain-water-ii/solution/cong-1djie-yu-shui-dao-2djie-yu-shui-si-i130l/

链接的大佬写的思路很清晰，结合视频进行学习。

6.代码

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

class Solution {
public:
    int trapRainWater(vector<vector<int> >& height)
    {
        int n = height.size(), m = height[0].size();//n为行，m为列
        priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > que;//构造最小堆
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < m; ++j)
            {
                if(i == 0 || j == 0 || i == n-1 || j == m-1)
                {
                    que.push({height[i][j], i*m + j});
                    height[i][j] = -1;
                }
            }
        }

        int x[4] = {0, 0, 1, -1}, y[4] = {1, -1, 0, 0};//表示查找当前元素上下右左四边是否有元素没有入堆，若有，不操作，若无，入堆

        int ans = 0, maxH = INT_MIN;//C++中常量INT_MAX和INT_MIN分别表示最大、最小整数，定义在头文件limits.h中
        while(!que.empty())
        {
            const auto& cur = que.top();//获取最小堆的最小元素
            int h = cur.first, i = cur.second/m, j = cur.second%m; //i和j表示当前元素的位置
            que.pop();
            if(h > maxH) maxH = h;
            for(int k = 0; k < 4; ++k)
            {
                i += x[k], j += y[k];//依次寻找当前元素的上下右左的元素是否入堆，并且检查该元素是否比maxH小，若小，则可以接雨水
                if(i >= 0 && i < n && j >= 0 && j < m && height[i][j] != -1)
                {
                    que.push({height[i][j], i*m + j});
                    if(height[i][j] < maxH) ans += maxH - height[i][j];
                    height[i][j] = -1;
                }
                i -= x[k], j -= y[k];//与上面的i和j返回原来的位置，即还是当前元素的位置，以便循环中查找下一个位置
            }
        }
        return ans;
    }
};

int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    int m, n,data;
    vector<vector<int> > heights;
    cin>>m>>n;
    for(int i=0; i<m; i++)
    {
        vector<int> row;
        for(int j=0; j<n; j++)
        {
            cin>>data;
            row.push_back(data);
        }
        heights.push_back(row);
    }

    int res=Solution().trapRainWater(heights);
    cout<<res<<endl;
    return 0;
}