每日一题(2022-01-29):地图中的最高点

每日一题(2022-01-29):地图中的最高点

来源:力扣
难度:中等
题目:1765. 地图中的最高点

题目详情

原题截图1.png
原题截图2.png

题解思路

提供两种思路解法,多源广度优先搜索动态规划

1. 多源广度优先搜索

简单来说就是由水域方格开始向四周逐层“生长”,每次“生长”生成的对应层的单元格高度增高1,新计算高度的单元格将会作为新的一层生长的基础高度;
有如下几个小技巧:

  • 使用队列记录新的影响点;
  • 需要记录陆地单元格是否已经被修改过;
  • “原地的”修改传入的矩阵可以节省内存;
class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int m = isWater.size(), n = isWater[0].size();
        // 计算地图单元格影响点的任务队列
        queue<pair<int, int>> queTask;
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                // 如果当前为水域单元格,则设置其高度,
                // 并将其作为地图的影响点添加至后续计算的任务队列
                if (isWater[i][j])
                {
                    isWater[i][j] = 0;
                    queTask.emplace(i, j);
                }
                // 否则为陆地单元格,设置其高度为 -1,
                // 以代表此单元格没有被访问修改过
                else
                    isWater[i][j] = -1;
            }
        }

        while (!queTask.empty())
        {
            const pair<int, int>& point = queTask.front();
            for (const vector<int>& direction : __m_vecDirections)
            {
                // 根据当前选择的方向,得到下一个需要计算高度的单元格索引
                int iNextX = point.first + direction[0];
                int iNextY = point.second + direction[1];
                // 如果当前单元格索引没有越界并且没有被访问修改过
                if (iNextX >= 0 && iNextX < m && iNextY >= 0 
                    && iNextY < n && isWater[iNextX][iNextY] == -1)
                {
                    // 将新单元格的高度增长 1
                    isWater[iNextX][iNextY] = isWater[point.first][point.second] + 1;
                    // 将刚刚计算高度完成的新单元格作为地图高度影响点加入到队列中
                    queTask.emplace(iNextX, iNextY);
                }
            }
            queTask.pop();
        }
        return isWater;
    }

private:
    // 上下左右四个方向向量
    vector<vector<int>> __m_vecDirections = 
    {
        { -1, 0 }, { 1, 0 },
        { 0, -1 }, { 0, 1 }
    };
};

运行结果.png

2. 动态规划

本题最经典的做法应该是动态规划;
由于每个单元格只受上下左右四个方向的单元格高度影响,所以可以通过从 “左上到右下,右下到左上” 两次遍历得到每个单元格的最小高度,在保证最小高度下进行递增,就可以确保相邻单元格最大高度差为1;
动态规划依然可以将传入的矩阵当做结果矩阵进行“原地的”操作;

class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int m = isWater.size(), n = isWater[0].size();

        // 初始化方格高度
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (isWater[i][j]) 
                    isWater[i][j] = 0;
                else
                    // 初始化为 INT_MAX - 1000 防止高度溢出
                    isWater[i][j] = INT_MAX - 1000;
        
        // 由左上到右下方向遍历计算单元格高度
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
            {
                // 如果当前单元格为水域则跳过
                if (isWater[i][j] == 0) continue;
                // 根据上方和左方单元格高度计算当前单元格的高度
                if (i > 0) isWater[i][j] = min(isWater[i - 1][j] + 1, isWater[i][j]);
                if (j > 0) isWater[i][j] = min(isWater[i][j - 1] + 1, isWater[i][j]);
            }
        
        // 由右下到左上方向遍历计算单元格高度
        for (int i = m - 1; i >= 0; --i)
            for (int j = n - 1; j >= 0; --j)
            {
                // 如果当前单元格为水域则跳过
                if (isWater[i][j] == 0) continue;
                // 根据下方和右方单元格高度计算当前单元格的高度
                if (i < m - 1) isWater[i][j] = min(isWater[i + 1][j] + 1, isWater[i][j]);
                if (j < n - 1) isWater[i][j] = min(isWater[i][j + 1] + 1, isWater[i][j]);
            }
        
        return isWater;
    }
};

运行结果.png