每日一题：9. 接雨水（C++）

每日一题：9. 接雨水（C++）

每日一题：9. 接雨水（C++）

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

解题思路：

1. 对矩阵进行判别，如果不是行列大于等于三则舍去（因为形成不了凹陷接水）
2. 先将边界记录进优先栈（从低到高，头为最低值），并且把记录的位置进行标记（存水多少根据最低位置而定）
3. 将栈从低到高输出，判断当前输出位置四周是否能够存水并且是否已经被利用过，若能够存水且没被标记则将结果加上能存的大小，并且进行标记说明利用过，将当前位置与村水后高度加入栈；如若不能存水也进行标记说明判断过，将自身位置与高度加入栈
4. 重复3 *** 作，从最低边界由一边到另一边将所有位置都遍历得到结果

代码

class Solution {
public:
    int trapRainWater(vector>& heightMap) {
        int m = heightMap.size(), n = heightMap[0].size(), result = 0;//定义mn保存矩阵行列数，result保存结果
        if(m < 3 || n < 3) {return 0;}                                //判断矩阵大小是否能够达到存水要求
        int temp_sign[] = {-1, 0, 1, 0, -1};                          //定义temp_sign数组，保存五个值，在下面用来判断输出位置四周能否存水
        vector> sign(m, vector(n, false));         //定义vector>变量sign来对所有位置进行标记是否判断过
        priority_queue, vector>, greater>> pq;//定义优先级栈pq从低到高保存位置与高度
        for(int i = 0; i < m; i ++){                                  //利用for循环将列边界记录进栈
            sign[i][0] = true;                                        //列的左边界进行标记
            pq.push({heightMap[i][0], i * n + 0});                    //进入栈
            sign[i][n - 1] = true;                                    //列的右边界进行标记
            pq.push({heightMap[i][n - 1], i * n + n - 1});            //进入栈
        }
        
        for(int i = 0; i < n; i ++){                                  //与上同理，将行边界记录进栈
            sign[0][i] = true;
            pq.push({heightMap[0][i], 0 * n + i});
            sign[m - 1][i] = true;
            pq.push({heightMap[m - 1][i], (m - 1) * n + i});
        }

        while(!pq.empty()){                                            //如果栈不是空的进行循环判断
            pair temp = pq.top();                            //取出当前位置
            pq.pop();                                                  //当前位置出栈
            for(int i = 0; i < 4; i ++){                               //利用定义temp_sign数组使用for循环取出当前位置的四周
                int a = temp.second / n + temp_sign[i], b = temp.second % n + temp_sign[i + 1];//a为四周位置的行下标，b为列下标
                if(a >= 0 && a < m && b >= 0 && b < n && !sign[a][b]){ //如果当前位置存在且没被标记过，进行判断
                    if(heightMap[a][b] < temp.first){                  //四周位置之一低于当前判断位置，能存水，结果加上存水大小
                        result += temp.first - heightMap[a][b];
                        }
                        pq.push({max(heightMap[a][b], temp.first), a * n + b});//将当前位置和存水后自身高度加入栈
                        sign[a][b] = true;                              //进行标记
                }
            }
        }
        return result;                                                   //返回结果
    }
};

作者：yi-si-cb（倚肆）
链接：https://leetcode-cn.com/problems/next-greater-element-i/solution/xie-shi-bao-li-suan-fa-by-yi-si-cb-dsk2/