LeetCode 题解工作台
地图分析
你现在手里有一份大小为 n x n 的 网格 grid ，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋， 1 代表陆地。 请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1 。 我们这里说的距离是「…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们可以将所有陆地单元格加入队列 中，如果队列为空，或者队列中元素个数等于网格中的单元格个数，则说明网格中只有陆地或者海洋，返回 。 否则，我们从陆地单元格开始进行广度优先搜索。定义初始步数 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。
请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。
我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
示例 1：
输入：grid = [[1,0,1],[0,0,0],[1,0,1]] 输出：2 解释： 海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。
示例 2：
输入：grid = [[1,0,0],[0,0,0],[0,0,0]] 输出：4 解释： 海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。
提示：
n == grid.lengthn == grid[i].length1 <= n <= 100grid[i][j]不是0就是1
解题思路
方法一：BFS
我们可以将所有陆地单元格加入队列 中，如果队列为空，或者队列中元素个数等于网格中的单元格个数，则说明网格中只有陆地或者海洋，返回 。
否则，我们从陆地单元格开始进行广度优先搜索。定义初始步数 。
在每一轮搜索中，我们将队列中的所有单元格向四个方向扩散，若单元格是海洋单元格，则将其标记为陆地单元格，并加入队列。在一轮扩散完成后，我们将步数加 。重复这一过程，直到队列为空。
最后，我们返回步数 。
时间复杂度 ，空间复杂度 。其中 是网格的边长。
class Solution:
def maxDistance(self, grid: List[List[int]]) -> int:
n = len(grid)
q = deque((i, j) for i in range(n) for j in range(n) if grid[i][j])
ans = -1
if len(q) in (0, n * n):
return ans
dirs = (-1, 0, 1, 0, -1)
while q:
for _ in range(len(q)):
i, j = q.popleft()
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < n and 0 <= y < n and grid[x][y] == 0:
grid[x][y] = 1
q.append((x, y))
ans += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space complexity depends on the final implementation. BFS typically has O(n^2) time complexity as it processes every cell, while the space complexity is O(n^2) for storing distance values in a grid. Optimizations may reduce space usage, but the time complexity remains tied to grid size. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate apply dynamic programming to transform the problem into a state transition problem?
- question_mark
Is the candidate able to connect BFS with dynamic programming techniques?
- question_mark
Does the candidate understand how BFS can propagate distance calculations efficiently across a grid?
常见陷阱
外企场景- error
Failing to apply BFS from all land cells at once, resulting in incorrect or incomplete distance values.
- error
Overcomplicating the problem by calculating distances individually for each water cell, instead of propagating distances from land to water.
- error
Not accounting for edge cases, such as when there are no land or no water cells in the grid.
进阶变体
外企场景- arrow_right_alt
Handling grids with more complex obstacles or barriers between land and water.
- arrow_right_alt
Extending the problem to include diagonal movement (chebyshev distance) instead of Manhattan distance.
- arrow_right_alt
Modifying the problem to find the nearest water cell to each land cell instead of the farthest water cell.