地图中的最高点

给你一个大小为 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) 的高度。如果有多种解法，请返回 任意一个 。

https://leetcode.cn/problems/map-of-highest-peak/

1. 多源BFS：时间复杂度n方，执行时间缩短 97.3% ： 1900ms - 50ms
2. 水源索引入队，BFS层层遍历

菜鸡解：

/** Copyright (c) Huawei Technologies Co., Ltd. 2023-2023. All rights reserved.*/package com.huawei.prac;import java.util.Arrays;class SolutionSt {public static void main(String[] args) {int[][] isWater = new int[][] {{0, 0, 1}, {1, 0, 0}, {0, 0, 0}};for (int[] arr : isWater) {Arrays.stream(arr).forEach(System.out::print);System.out.println();}System.out.println("============================");int[][] resArr = highestPeak(isWater);for (int[] arr : resArr) {Arrays.stream(arr).forEach(System.out::print);System.out.println();}}/*** 765. 地图中的最高点* 三层循环，味同嚼蜡，目不忍视** @param isWater 陆地水域地图二维数组* @return 高度矩阵，使得矩阵中的最高高度值 最大*/public static int[][] highestPeak(int[][] isWater) {boolean isExist;int maxVal = 1;int row = isWater.length;int col = isWater[0].length;boolean[][] visited = new boolean[row][col];for (int i = 0; i < maxVal; i++) {isExist = isChangeMatrix(isWater, maxVal, visited);maxVal = isExist ? maxVal + 1 : maxVal;}for (int i = 0; i < row; i++) {for (int j = 0; j < col; j++) {isWater[i][j] -= 1;}}return isWater;}private static boolean isChangeMatrix(int[][] isWater, int maxVal, boolean[][] visited) {int row = isWater.length;int col = isWater[0].length;boolean isExist = false;for (int j = 0; j < row; j++) {for (int k = 0; k < col; k++) {if (isWater[j][k] == maxVal) {isExist = isChange(isWater, maxVal, visited, row, col, isExist, j, k);}}}return isExist;}private static boolean isChange(int[][] isWater, int maxVal, boolean[][] visited, int row, int col, boolean isExist,int j, int k) {visited[j][k] = true;if (j - 1 >= 0 && !visited[j - 1][k] && isWater[j - 1][k] != maxVal) {isWater[j - 1][k] = maxVal + 1;visited[j - 1][k] = true;isExist = true;}if (j + 1 < row && !visited[j + 1][k] && isWater[j + 1][k] != maxVal) {isWater[j + 1][k] = maxVal + 1;visited[j + 1][k] = true;isExist = true;}if (k - 1 >= 0 && !visited[j][k - 1] && isWater[j][k - 1] != maxVal) {isWater[j][k - 1] = maxVal + 1;visited[j][k - 1] = true;isExist = true;}if (k + 1 < col && !visited[j][k + 1] && isWater[j][k + 1] != maxVal) {isWater[j][k + 1] = maxVal + 1;visited[j][k + 1] = true;isExist = true;}return isExist;}
}

大佬解

/** Copyright (c) Huawei Technologies Co., Ltd. 2023-2023. All rights reserved.*/package com.huawei.prac;import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;class SolutionRd {public static void main(String[] args) {int[][] isWater = new int[][] {{0, 0, 1}, {1, 0, 0}, {0, 0, 0}};for (int[] arr : isWater) {Arrays.stream(arr).forEach(System.out::print);System.out.println();}System.out.println("============================");int[][] resArr = highestPeak(isWater);for (int[] arr : resArr) {Arrays.stream(arr).forEach(System.out::print);System.out.println();}}/*** 765. 地图中的最高点[多源BFS]* 时间复杂度n方，执行时间缩短 97.3% ： 1900ms - 50ms** @param isWater 陆地水域地图二维数组* @return 高度矩阵，使得矩阵中的最高高度值 最大*/public static int[][] highestPeak(int[][] isWater) {Queue queue = new ArrayDeque<>();int[][] resArr = new int[isWater.length][isWater[0].length];// 上 下 左 右 移动int[][] direc = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// 水源入队，陆地赋值-1for (int i = 0; i < isWater.length; i++) {for (int j = 0; j < isWater[0].length; j++) {if (isWater[i][j] == 1) {queue.offer(new int[] {i, j});} else {resArr[i][j] = -1;}}}// BFSwhile (!queue.isEmpty()) {int[] arr = queue.poll();for (int[] ints : direc) {int rowNext = arr[0] + ints[0];int colNext = arr[1] + ints[1];if (invalid(rowNext, colNext, resArr)) {continue;}resArr[rowNext][colNext] = resArr[arr[0]][arr[1]] + 1;queue.offer(new int[] {rowNext, colNext});}}return resArr;}private static boolean invalid(int rowNext, int colNext, int[][] arr) {return rowNext >= arr.length || rowNext < 0 || colNext >= arr[0].length || colNext < 0|| arr[rowNext][colNext] != -1;}
}