地图中的最高点

标签: 广度优先搜索数组矩阵

难度: 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 个水域格子。

Submission

运行时间: 550 ms

内存: 80.1 MB

class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        from collections import deque

        # def BFS(cell,heights):
        #     q = deque()
        #     q.append([cell[0],cell[1],0])
        #     while len(q) > 0:
        #         ele = q.popleft()
        #         x,y,level = ele[0],ele[1],ele[2]
        #         if y>0 and (heights[x][y-1] < 0 or abs(heights[x][y-1]-level) > 1):
        #             if heights[x][y-1] != 0:
        #                 heights[x][y-1] = level + 1
        #                 q.append([x,y-1,level+1])
        #         if y<n-1 and (heights[x][y+1] < 0 or abs(heights[x][y+1]-level) > 1):
        #             if heights[x][y+1] != 0:
        #                 heights[x][y+1] = level + 1
        #                 q.append([x,y+1,level+1])
        #         if x>0 and (heights[x-1][y] < 0 or abs(heights[x-1][y]-level) > 1):
        #             if heights[x-1][y] != 0:
        #                 heights[x-1][y] = level + 1
        #                 q.append([x-1,y,level+1])
        #         if x<m-1 and (heights[x+1][y] < 0 or abs(heights[x+1][y]-level) > 1):
        #             if heights[x+1][y] != 0:
        #                 heights[x+1][y] = level + 1
        #                 q.append([x+1,y,level+1])
                

        m = len(isWater)
        n = len(isWater[0])
        heights = [[-1]*n for i in range(m)]
        # waterCell = []
        # for i in range(m):
        #     for j in range(n):
        #         if isWater[i][j] == 1:
        #             heights[i][j] = 0
        #             waterCell.append([i,j])
        # for cell in waterCell:
        #     BFS(cell,heights)
        # return heights

        q = deque()
        for i in range(m):
            for j in range(n):
                if isWater[i][j] == 1:
                    q.append([i,j,0])
                    heights[i][j] = 0
        while len(q) > 0:
            ele = q.popleft()
            x,y,level = ele[0],ele[1],ele[2]
            if y>0 and heights[x][y-1] == -1:
                heights[x][y-1] = level+1
                q.append([x,y-1,level+1])
            if y<n-1 and heights[x][y+1] == -1:
                heights[x][y+1] = level+1
                q.append([x,y+1,level+1])
            if x>0 and heights[x-1][y] == -1:
                heights[x-1][y] = level+1
                q.append([x-1,y,level+1])
            if x<m-1 and heights[x+1][y] == -1:
                heights[x+1][y] = level+1
                q.append([x+1,y,level+1])
        return heights

Explain

本题使用宽度优先搜索（BFS）的方式从每个水域（高度为0的单元格）开始向外扩展，为陆地单元格设置高度。我们使用一个队列来实现BFS，并在过程中记录每个单元格的高度。我们首先初始化所有水域单元格的高度为0并将它们加入队列。接着，对于队列中的每个元素，我们检查它的四个邻居单元格（上下左右）。如果某个邻居单元格的高度尚未被设置（即初始化的-1值），我们将其高度设置为当前单元格的高度加一，并将该邻居单元格加入队列中继续处理。这种方式保证了相邻单元格的高度差不会超过1，并且从水源开始最远的陆地单元格会获得最大的高度值。

时间复杂度: O(m * n)

空间复杂度: O(m * n)

class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        from collections import deque

        m = len(isWater)
        n = len(isWater[0])
        heights = [[-1]*n for i in range(m)]  # 初始化高度矩阵，未设定的单元格高度为-1

        q = deque()
        for i in range(m):  # 遍历所有单元格，将水域单元格加入队列
            for j in range(n):
                if isWater[i][j] == 1:
                    q.append([i,j,0])
                    heights[i][j] = 0  # 水域高度设置为0
        while len(q) > 0:
            ele = q.popleft()
            x, y, level = ele[0], ele[1], ele[2]
            # 依次检查当前单元格的四个邻居
            if y > 0 and heights[x][y-1] == -1:  # 检查左邻居
                heights[x][y-1] = level+1
                q.append([x, y-1, level+1])
            if y < n-1 and heights[x][y+1] == -1:  # 检查右邻居
                heights[x][y+1] = level+1
                q.append([x, y+1, level+1])
            if x > 0 and heights[x-1][y] == -1:  # 检查上邻居
                heights[x-1][y] = level+1
                q.append([x-1, y, level+1])
            if x < m-1 and heights[x+1][y] == -1:  # 检查下邻居
                heights[x+1][y] = level+1
                q.append([x+1, y, level+1])
        return heights

Explore

在初始化高度矩阵时，使用-1作为未设定高度的标志有几个原因：首先，-1在这种场景中通常不存在自然含义，因此可以清楚地表示该单元格尚未处理。其次，使用负数可以方便地与正常的高度值（从0开始）区分开来。当然，也可以使用其他方式表示未设定的高度，如使用 `None` 或者一个特定的常量。然而，使用-1可以直接在整数数组中操作，简化代码实现，并提高效率。

在队列中包括当前高度信息确实有些重复，因为相同的信息可以从 `heights` 矩阵中直接获取。通过只将坐标加入队列，并在需要时从 `heights` 矩阵中查询高度，可以稍微减少每个队列元素所占的内存。然而，将高度信息包含在队列中可以减少从 `heights` 矩阵的重复查询操作，从而可能提升一些运行效率。具体使用哪种方式，需要根据实际情况和优化需求来决定。

在算法中确实存在重复检查邻居的可能性，因为每个单元格在被处理时都会检查其四个邻居，而每个邻居本身也会作为中心被检查。然而，这种重复检查对性能的影响是有限的，因为一个单元格一旦被设置了高度并被加入队列，就不会再次被加入队列。虽然算法会检查每个邻居是否已被设定高度，但只有未设定的邻居会被加入队列。这种重复检查确保了代码的简洁性和正确性，且额外的检查成本相对较低。

最坏情况下所有单元格都需要被访问的情况发生在地图中的水域单元格只有一个，且位于地图的一个角落或边缘，而其余全部是陆地单元格。在这种情况下，BFS需要从这个单一的水域单元格开始，向外逐渐扩展到地图的每一个角落，以确保每个陆地单元格的高度都被正确计算。这意味着每个单元格至少被访问一次以设置其高度。