LeetCode 题解工作台
包含所有 1 的最小矩形面积 I
给你一个二维 二进制 数组 grid 。请你找出一个边在水平方向和竖直方向上、面积 最小 的矩形，并且满足 grid 中所有的 1 都在矩形的内部。 返回这个矩形可能的 最小 面积。 示例 1： 输入： grid = [[0,1,0],[1,0,1]] 输出： 6 解释： 这个最小矩形的高度为 2，…
2
题型
8
代码语言
3
相关题
当前训练重点
中等 · 数组·matrix
答案摘要
我们可以遍历 `grid`，找到所有 `1` 的最小边界，记为 $(x_1, y_1)$，最大边界，记为 $(x_2, y_2)$，那么最小矩形的面积就是 $(x_2 - x_1 + 1) \times (y_2 - y_1 + 1)$。 时间复杂度 $O(m \times n)$，其中 和 分别是 `grid` 的行数和列数。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·matrix 题型思路
题目描述
给你一个二维 二进制 数组 grid。请你找出一个边在水平方向和竖直方向上、面积 最小 的矩形，并且满足 grid 中所有的 1 都在矩形的内部。
返回这个矩形可能的 最小 面积。
示例 1：
输入： grid = [[0,1,0],[1,0,1]]
输出： 6
解释：
这个最小矩形的高度为 2，宽度为 3，因此面积为 2 * 3 = 6。
示例 2：
输入： grid = [[0,0],[1,0]]
输出： 1
解释：
这个最小矩形的高度和宽度都是 1，因此面积为 1 * 1 = 1。
提示：
1 <= grid.length, grid[i].length <= 1000grid[i][j]是 0 或 1。- 输入保证
grid中至少有一个 1 。
解题思路
方法一：求最小边界和最大边界
我们可以遍历 grid，找到所有 1 的最小边界，记为 ，最大边界，记为 ，那么最小矩形的面积就是 。
时间复杂度 ，其中 和 分别是 grid 的行数和列数。空间复杂度 。
class Solution:
def minimumArea(self, grid: List[List[int]]) -> int:
x1 = y1 = inf
x2 = y2 = -inf
for i, row in enumerate(grid):
for j, x in enumerate(row):
if x == 1:
x1 = min(x1, i)
y1 = min(y1, j)
x2 = max(x2, i)
y2 = max(y2, j)
return (x2 - x1 + 1) * (y2 - y1 + 1)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate should efficiently identify the boundaries of the rectangle.
- question_mark
They should avoid unnecessary iterations or reprocessing of the grid.
- question_mark
A good solution will have O(n * m) time complexity with constant space usage.
常见陷阱
外企场景- error
Failing to correctly identify the boundaries of the rectangle.
- error
Overcomplicating the problem by using extra data structures.
- error
Incorrectly calculating the area after finding the bounds.
进阶变体
外企场景- arrow_right_alt
Consider the case when the grid has only one 1.
- arrow_right_alt
What if the grid has a large number of 1's, and performance is a concern?
- arrow_right_alt
How would you handle grids where the 1's are distributed sparsely?