每日一题:LeetCode:1765.地图中最高的点

浏览次数 : 次 2022-01-29

博文字数统计 : 1.1k字 | 阅读所需时长 : 4分

× 文章目录

1. 2022-01-29：LeetCode：1765.地图中最高的点
1. 1.1. 1. 题目描述
2. 1.2. 2. 方法一：多源BFS

每日一题：LeetCode：1765.地图中最高的点
- 时间：2022-01-29
- 力扣难度：Medium
- 个人难度：Medium
- 数据结构：数组
- 算法：多源BFS

2022-01-29：LeetCode：1765.地图中最高的点

1. 题目描述

题目：原题链接
- 给你一个大小为 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) 的高度。如果有多种解法，请返回任意一个。
- m == isWater.length
- n == isWater[i].length
- 1 <= m, n <= 1000
- isWater[i][j] 要么是 0 ，要么是 1 。
- 至少有 1 个水域格子
输入输出规范
- 输入：二维数组，表示陆地和水域
- 输出：二维数组，每个位置的高度
输入输出示例
- 输入：isWater = [[0,1],[0,0]]
- 输出：[[1,0],[2,1]]

2. 方法一：多源BFS

思路
- 本题需要求解网格中每个点的最大高度，且规定了水域的值为0，相邻的网格之间最大差值为1
- 问题实际上可以转化为，一个表示陆地的网格，到离它最近的水域网格的距离，因为水域网格有多个，所以是通过多源BFS来求解
- 首先，维护一个队列，用来保存我们的起点的坐标(数组形式)，先遍历网格，将水域对应的坐标全部加入队列
- 然后，遍历该队列，取出队首元素，每一次根据上下左右四个方向模拟周围的情况，因为相邻的元素的高度最多只能差1，而且要求的是最大高度，所以四周的元素的高度应该为中间元素的高度+1
- 且对于已经求出高度的元素，不应该再次被遍历计算，因为这样可能会改变其高度值，导致不满足相邻高度差最多是1的限制，因此使用一个 visited 数组表示元素是否计算过
- 实际上，也可以不使用额外的 visited 数组，直接将结果数组赋值一个不会取到的初始值，如 -1、Integer.MAX_VALUE等，通过元素值是否为初始值来判断是否访问过即可
- 此外，本题还可以结合原地算法，直接在输入的数组中进行操作，最后返回该数组即可，具体方法是在第一次遍历输入的二维数组，将水域位置的坐标入队时，将陆地的坐标赋值为上面提到的初始值即可

题解

public int[][] highestPeak(int[][] isWater) {
    if (isWater == null || isWater.length == 0) return null;
    int m = isWater.length;
    int n = isWater[0].length;
    Deque<int[]> deque = new LinkedList<>();
    int[][] height = new int[m][n];
    for (int i = 0; i < m; i++) {
        Arrays.fill(height[i], -1);
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (isWater[i][j] == 1) {
                height[i][j] = 0;
                deque.add(new int[]{i, j});
            }
        }
    }
    int[][] dirs = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    while (!deque.isEmpty()) {
        int[] cur = deque.poll();
        int x = cur[0], y = cur[1];
        for (int[] dir : dirs) {
            int nx = x + dir[0], ny = y + dir[1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && height[nx][ny] == -1) {
                height[nx][ny] = height[x][y] + 1;
                deque.add(new int[]{nx, ny});
            }
        }
    }
    return height;
}

复杂度分析：m、n 是二维数组的长度
- 时间复杂度：$O(m*n)$
- 空间复杂度：$O(m*n)$

本文作者： Chthollists
发布时间： 2022-01-29 18:06:18
最后更新： 2022-02-20 13:34:08
本文标题： 每日一题:LeetCode:1765.地图中最高的点
本文链接： https://chthollists.github.io/post/457d7d62.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！