Medium

题目描述

给你一个大小为 m x n 的整数矩阵 isWater ，它代表了一个由陆地和水域单元格组成的地图。

  • 如果 isWater[i][j] == 0 ，格子 (i, j) 是一个 陆地 格子。
  • 如果 isWater[i][j] == 1 ，格子 (i, j) 是一个 水域 格子。

你必须按照如下规则给每个单元格安排高度：

  • 每个格子的高度都必须是 非负 的。
  • 如果一个格子是 水域 ，那么它的高度必须为 0 。
  • 任意相邻的格子高度差 至多 为 1 。当两个格子在正北、正东、正南、正西方向上相互紧挨着时，它们就是相邻的格子。（也就是说它们有一条公共边）

找到一种安排高度的方案，使得矩阵中的 最高 高度值 最大 。

请你返回一个大小为 m x n 的整数矩阵 height ，其中 height[i][j] 是格子 (i, j) 的高度。如果有多种解法，请返回 任意一个 。

示例 1：

输入：isWater = [[0,1],[0,0]]
输出：[[1,0],[2,1]]
解释：上图展示了给各个格子安排的高度。
蓝色格子是水域格子，绿色格子是陆地格子。

示例 2：

输入：isWater = [[0,0,1],[1,0,0],[0,0,0]]
输出：[[1,1,0],[0,1,1],[1,2,2]]
解释：所有安排方案中，最高的高度为 2 。
任意满足上述规则且最高高度为 2 的安排都是正确的。

提示：

  • m == isWater.length
  • n == isWater[i].length
  • 1 <= m, n <= 1000
  • isWater[i][j] 不是 0 就是 1 。
  • 至少有 1 个水域格子。

解题思路

这道题本质上是求矩阵中每个陆地格子到最近水域的距离，然后将这个距离作为高度。我们可以使用多源BFS来解决。

核心思路：

  1. 水域格子的高度必须为0，这是我们的起点
  2. 相邻格子高度差最多为1，这意味着距离水域越远的格子，高度越高
  3. 每个格子的高度就是它到最近水域的曼哈顿距离

算法步骤：

  1. 将所有水域格子作为起点加入队列，高度设为0
  2. 对所有陆地格子初始化高度为-1（表示未访问）
  3. 进行BFS遍历：
    • 从队列中取出当前格子
    • 遍历其四个相邻方向
    • 如果相邻格子是未访问的陆地格子，则其高度为当前格子高度+1
    • 将该格子加入队列继续处理

这种方法保证了每个格子都能获得到最近水域的最短距离作为高度，从而使得相邻格子高度差不超过1，并且能够最大化矩阵中的最高高度值。

时间复杂度为O(m×n)，因为每个格子只会被访问一次。空间复杂度也是O(m×n)，主要用于队列存储。

代码实现

class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int m = isWater.size(), n = isWater[0].size();
        vector<vector<int>> height(m, vector<int>(n, -1));
        queue<pair<int, int>> q;
        
        // 将所有水域格子作为起点
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isWater[i][j] == 1) {
                    height[i][j] = 0;
                    q.push({i, j});
                }
            }
        }
        
        int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            
            for (auto& dir : dirs) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && height[nx][ny] == -1) {
                    height[nx][ny] = height[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
        
        return height;
    }
};

class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        m, n = len(isWater), len(isWater[0])
        height = [[-1] * n for _ in range(m)]
        queue = deque()
        
        # 将所有水域格子作为起点
        for i in range(m):
            for j in range(n):
                if isWater[i][j] == 1:
                    height[i][j] = 0
                    queue.append((i, j))
        
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        while queue:
            x, y = queue.popleft()
            
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                
                if 0 <= nx < m and 0 <= ny < n and height[nx][ny] == -1:
                    height[nx][ny] = height[x][y] + 1
                    queue.append((nx, ny))
        
        return height

public class Solution {
    public int[][] HighestPeak(int[][] isWater) {
        int m = isWater.Length, n = isWater[0].Length;
        int[][] height = new int[m][];
        for (int i = 0; i < m; i++) {
            height[i] = new int[n];
            for (int j = 0; j < n; j++) {
                height[i][j] = -1;
            }
        }
        
        Queue<int[]> queue = new Queue<int[]>();
        
        // 将所有水域格子作为起点
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isWater[i][j] == 1) {
                    height[i][j] = 0;
                    queue.Enqueue(new int[]{i, j});
                }
            }
        }
        
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (queue.Count > 0) {
            int[] current = queue.Dequeue();
            int x = current[0], y = current[1];
            
            foreach (int[] dir in directions) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && height[nx][ny] == -1) {
                    height[nx][ny] = height[x][y] + 1;
                    queue.Enqueue(new int[]{nx, ny});
                }
            }
        }
        
        return height;
    }
}

var highestPeak = function(isWater) {
    const m = isWater.length;
    const n = isWater[0].length;
    const result = Array(m).fill().map(() => Array(n).fill(-1));
    const queue = [];
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (isWater[i][j] === 1) {
                result[i][j] = 0;
                queue.push([i, j]);
            }
        }
    }
    
    while (queue.length > 0) {
        const [row, col] = queue.shift();
        
        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;
            
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && result[newRow][newCol] === -1) {
                result[newRow][newCol] = result[row][col] + 1;
                queue.push([newRow, newCol]);
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m × n)每个格子只会被访问一次，其中m和n分别为矩阵的行数和列数
空间复杂度O(m × n)需要额外的height矩阵存储结果，队列最坏情况下可能存储所有格子