LeetCode 题解工作台
包含所有 1 的最小矩形面积 II
给你一个二维 二进制 数组 grid 。你需要找到 3 个 不重叠 、面积 非零 、边在水平方向和竖直方向上的矩形，并且满足 grid 中所有的 1 都在这些矩形的内部。 返回这些矩形面积之和的 最小 可能值。 注意 ，这些矩形可以相接。 示例 1： 输入： grid = [[1,0,1],[1,1…
3
题型
8
代码语言
3
相关题
当前训练重点
困难 · 数组·matrix
答案摘要
根据题目描述，我们可以用两条分割线，将矩形分成三个部分，我们分别计算每一部分包含所有 的最小矩形面积，然后取三个部分面积之和的最小值。 我们可以枚举两条分割线的位置，共有 种情况：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·matrix 题型思路
题目描述
给你一个二维 二进制 数组 grid。你需要找到 3 个 不重叠、面积 非零 、边在水平方向和竖直方向上的矩形，并且满足 grid 中所有的 1 都在这些矩形的内部。
返回这些矩形面积之和的 最小 可能值。
注意，这些矩形可以相接。
示例 1：
输入： grid = [[1,0,1],[1,1,1]]
输出： 5
解释：
- 位于
(0, 0)和(1, 0)的 1 被一个面积为 2 的矩形覆盖。 - 位于
(0, 2)和(1, 2)的 1 被一个面积为 2 的矩形覆盖。 - 位于
(1, 1)的 1 被一个面积为 1 的矩形覆盖。
示例 2：
输入： grid = [[1,0,1,0],[0,1,0,1]]
输出： 5
解释：
- 位于
(0, 0)和(0, 2)的 1 被一个面积为 3 的矩形覆盖。 - 位于
(1, 1)的 1 被一个面积为 1 的矩形覆盖。 - 位于
(1, 3)的 1 被一个面积为 1 的矩形覆盖。
提示：
1 <= grid.length, grid[i].length <= 30grid[i][j]是 0 或 1。- 输入保证
grid中至少有三个 1 。
解题思路
方法一：枚举
根据题目描述，我们可以用两条分割线，将矩形分成三个部分，我们分别计算每一部分包含所有 的最小矩形面积，然后取三个部分面积之和的最小值。
我们可以枚举两条分割线的位置，共有 种情况：
- 两次横向分割
- 两次纵向分割
- 先进行一次横向分割，再对上部分进行一次纵向分割
- 先进行一次横向分割，再对下部分进行一次纵向分割
- 先进行一次纵向分割，再对左部分进行一次横向分割
- 先进行一次纵向分割，再对右部分进行一次横向分割
我们可以用一个函数 来计算矩形 到 包含所有 的最小矩形面积。
时间复杂度 ，其中 和 分别是矩形的行数和列数。空间复杂度 。
class Solution:
def minimumSum(self, grid: List[List[int]]) -> int:
def f(i1: int, j1: int, i2: int, j2: int) -> int:
x1 = y1 = inf
x2 = y2 = -inf
for i in range(i1, i2 + 1):
for j in range(j1, j2 + 1):
if grid[i][j] == 1:
x1 = min(x1, i)
y1 = min(y1, j)
x2 = max(x2, i)
y2 = max(y2, j)
return (x2 - x1 + 1) * (y2 - y1 + 1)
m, n = len(grid), len(grid[0])
ans = m * n
for i1 in range(m - 1):
for i2 in range(i1 + 1, m - 1):
ans = min(
ans,
f(0, 0, i1, n - 1)
+ f(i1 + 1, 0, i2, n - 1)
+ f(i2 + 1, 0, m - 1, n - 1),
)
for j1 in range(n - 1):
for j2 in range(j1 + 1, n - 1):
ans = min(
ans,
f(0, 0, m - 1, j1)
+ f(0, j1 + 1, m - 1, j2)
+ f(0, j2 + 1, m - 1, n - 1),
)
for i in range(m - 1):
for j in range(n - 1):
ans = min(
ans,
f(0, 0, i, j) + f(0, j + 1, i, n - 1) + f(i + 1, 0, m - 1, n - 1),
)
ans = min(
ans,
f(0, 0, i, n - 1)
+ f(i + 1, 0, m - 1, j)
+ f(i + 1, j + 1, m - 1, n - 1),
)
ans = min(
ans,
f(0, 0, i, j) + f(i + 1, 0, m - 1, j) + f(0, j + 1, m - 1, n - 1),
)
ans = min(
ans,
f(0, 0, m - 1, j)
+ f(0, j + 1, i, n - 1)
+ f(i + 1, j + 1, m - 1, n - 1),
)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Strong understanding of dynamic programming or backtracking.
- question_mark
Ability to optimize grid-based problems with enumeration.
- question_mark
Clear approach to solving problems involving minimizing area and avoiding overlap.
常见陷阱
外企场景- error
Failing to handle cases where rectangles must touch but not overlap.
- error
Overcomplicating the enumeration of potential rectangles.
- error
Missing optimization steps to minimize the area of rectangles.
进阶变体
外企场景- arrow_right_alt
Extending the problem to cover more than three rectangles.
- arrow_right_alt
Considering different shapes of rectangles (not just aligned with axes).
- arrow_right_alt
Handling grids with larger sizes (e.g., up to 100x100).