LeetCode 题解工作台
最大加号标志
在一个 n x n 的矩阵 grid 中，除了在数组 mines 中给出的元素为 0 ，其他每个元素都为 1 。 mines[i] = [x i , y i ] 表示 grid[x i ][y i ] == 0 返回 grid 中包含 1 的最大的 轴对齐 加号标志的阶数 。如果未找到加号标志，则返…
2
题型
4
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们定义 表示以 $(i, j)$ 为中心的最大加号标志的阶数，答案即为所有 的最大值。 我们可以发现，对于每个 $(i, j)$，其最大加号标志的阶数不会超过其上下左右四个方向上连续的 的个数的最小值。因此，我们可以预处理出每个位置上下左右四个方向上连续的 的个数，然后遍历所有的 $(i, j)$，求出 的最大值即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
在一个 n x n 的矩阵 grid 中，除了在数组 mines 中给出的元素为 0，其他每个元素都为 1。mines[i] = [xi, yi]表示 grid[xi][yi] == 0
返回 grid 中包含 1 的最大的 轴对齐 加号标志的阶数 。如果未找到加号标志，则返回 0 。
一个 k 阶由 1 组成的 “轴对称”加号标志 具有中心网格 grid[r][c] == 1 ，以及4个从中心向上、向下、向左、向右延伸，长度为 k-1，由 1 组成的臂。注意，只有加号标志的所有网格要求为 1 ，别的网格可能为 0 也可能为 1 。
示例 1：
输入: n = 5, mines = [[4, 2]] 输出: 2 解释: 在上面的网格中，最大加号标志的阶只能是2。一个标志已在图中标出。
示例 2：
输入: n = 1, mines = [[0, 0]] 输出: 0 解释: 没有加号标志，返回 0 。
提示：
1 <= n <= 5001 <= mines.length <= 50000 <= xi, yi < n- 每一对
(xi, yi)都 不重复
解题思路
方法一：动态规划
我们定义 表示以 为中心的最大加号标志的阶数，答案即为所有 的最大值。
我们可以发现，对于每个 ，其最大加号标志的阶数不会超过其上下左右四个方向上连续的 的个数的最小值。因此，我们可以预处理出每个位置上下左右四个方向上连续的 的个数，然后遍历所有的 ，求出 的最大值即可。
时间复杂度 ，空间复杂度 。其中 为网格的边长。
class Solution:
def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
dp = [[n] * n for _ in range(n)]
for x, y in mines:
dp[x][y] = 0
for i in range(n):
left = right = up = down = 0
for j, k in zip(range(n), reversed(range(n))):
left = left + 1 if dp[i][j] else 0
right = right + 1 if dp[i][k] else 0
up = up + 1 if dp[j][i] else 0
down = down + 1 if dp[k][i] else 0
dp[i][j] = min(dp[i][j], left)
dp[i][k] = min(dp[i][k], right)
dp[j][i] = min(dp[j][i], up)
dp[k][i] = min(dp[k][i], down)
return max(max(v) for v in dp)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N^2) |
| 空间 | O(N^2) |
面试官常问的追问
外企场景- question_mark
Can the candidate implement the dynamic programming approach efficiently?
- question_mark
Does the candidate handle edge cases such as fully blocked grids or small grids?
- question_mark
Is the candidate able to optimize the approach and avoid unnecessary recomputations?
常见陷阱
外企场景- error
Not initializing the dynamic programming tables correctly for the four directions.
- error
Overlooking edge cases where the grid is small or fully blocked.
- error
Failing to correctly compute the minimum arm length for each center of a plus sign.
进阶变体
外企场景- arrow_right_alt
Change the grid size or mine distribution to test the scalability of the solution.
- arrow_right_alt
Modify the problem to allow arbitrary values in the grid (not just 1's and 0's).
- arrow_right_alt
Optimize for larger grids and more mines, while maintaining correctness.