LeetCode 题解工作台
最大的以 1 为边界的正方形
给你一个由若干 0 和 1 组成的二维网格 grid ，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0 。 示例 1： 输入： grid = [[1,1,1],[1,0,1],[1,1,1]] 输出： 9 示例 2： 输入： grid = [[…
3
题型
4
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们可以使用前缀和的方法预处理出每个位置向下和向右的连续 的个数，记为 `down[i][j]` 和 `right[i][j]`。 然后我们枚举正方形的边长 ，从最大的边长开始枚举，然后枚举正方形的左上角位置 $(i, j)$，如果满足条件，即可返回 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。
示例 1：
输入：grid = [[1,1,1],[1,0,1],[1,1,1]] 输出：9
示例 2：
输入：grid = [[1,1,0,0]] 输出：1
提示：
1 <= grid.length <= 1001 <= grid[0].length <= 100grid[i][j]为0或1
解题思路
方法一：前缀和 + 枚举
我们可以使用前缀和的方法预处理出每个位置向下和向右的连续 的个数，记为 down[i][j] 和 right[i][j]。
然后我们枚举正方形的边长 ，从最大的边长开始枚举，然后枚举正方形的左上角位置 ，如果满足条件，即可返回 。
时间复杂度 ，空间复杂度 。其中 和 分别是网格的行数和列数。
class Solution:
def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
down = [[0] * n for _ in range(m)]
right = [[0] * n for _ in range(m)]
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
if grid[i][j]:
down[i][j] = down[i + 1][j] + 1 if i + 1 < m else 1
right[i][j] = right[i][j + 1] + 1 if j + 1 < n else 1
for k in range(min(m, n), 0, -1):
for i in range(m - k + 1):
for j in range(n - k + 1):
if (
down[i][j] >= k
and right[i][j] >= k
and right[i + k - 1][j] >= k
and down[i][j + k - 1] >= k
):
return k * k
return 0
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate understands dynamic programming for grid-based problems.
- question_mark
The candidate considers space and time complexity and aims for optimization.
- question_mark
The candidate uses state transitions effectively to track and update valid solutions.
常见陷阱
外企场景- error
Not considering the boundary conditions properly when constructing the dynamic programming table.
- error
Misunderstanding the problem requirement, where 1s should appear on all four borders of the square.
- error
Ignoring the impact of grid size on the time and space complexity when scaling up the problem.
进阶变体
外企场景- arrow_right_alt
Consider handling grids with varying dimensions or sparse 1s.
- arrow_right_alt
Try solving the problem with optimizations to reduce memory usage.
- arrow_right_alt
Explore different ways to handle grid cells, such as through greedy approaches or matrix manipulation.