当前位置：首页 > news >正文

豆包 LeetCode 3197. 包含所有 1 的最小矩形面积 II Java实现

news 2026/6/13 10:05:16

题目大意

给定一个二维二进制矩阵，用 3 个互不重叠、面积非零的轴对齐矩形覆盖矩阵中所有的 1，矩形可以相接但不能重叠，求三个矩形的面积之和的最小值。
数据范围：矩阵行列数均不超过 30。

核心思路

所有合法的三矩形不重叠布局，都可以归为以下 6 类切割模式，只需枚举所有切割线的位置，计算每种模式下的最小面积和，最终取全局最小值即可：

1. 两条水平切割线，将矩阵分为上、中、下三部分
2. 两条竖直切割线，将矩阵分为左、中、右三部分
3. 一条水平切割线分为上下，上半部分再用一条竖直切割线拆分
4. 一条水平切割线分为上下，下半部分再用一条竖直切割线拆分
5. 一条竖直切割线分为左右，左半部分再用一条水平切割线拆分
6. 一条竖直切割线分为左右，右半部分再用一条水平切割线拆分

对每个切割后的子区域，计算其内部所有 1 的最小包围矩形面积，求和后更新最小值。

Java 完整实现

java
class Solution {
public int minimumSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int minSum = Integer.MAX_VALUE;

// 1. 两条水平分割线：上、中、下三部分
for (int i = 0; i < m - 1; i++) {
for (int j = i + 1; j < m - 1; j++) {
int top = calcArea(grid, 0, 0, i, n - 1);
int mid = calcArea(grid, i + 1, 0, j, n - 1);
int bot = calcArea(grid, j + 1, 0, m - 1, n - 1);
minSum = Math.min(minSum, top + mid + bot);
}
}

// 2. 两条竖直分割线：左、中、右三部分
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n - 1; j++) {
int left = calcArea(grid, 0, 0, m - 1, i);
int mid = calcArea(grid, 0, i + 1, m - 1, j);
int right = calcArea(grid, 0, j + 1, m - 1, n - 1);
minSum = Math.min(minSum, left + mid + right);
}
}

// 3. 水平分割后，上半部分再竖直分割
for (int hori = 0; hori < m - 1; hori++) {
for (int vert = 0; vert < n - 1; vert++) {
int topLeft = calcArea(grid, 0, 0, hori, vert);
int topRight = calcArea(grid, 0, vert + 1, hori, n - 1);
int bottom = calcArea(grid, hori + 1, 0, m - 1, n - 1);
minSum = Math.min(minSum, topLeft + topRight + bottom);
}
}

// 4. 水平分割后，下半部分再竖直分割
for (int hori = 0; hori < m - 1; hori++) {
for (int vert = 0; vert < n - 1; vert++) {
int top = calcArea(grid, 0, 0, hori, n - 1);
int botLeft = calcArea(grid, hori + 1, 0, m - 1, vert);
int botRight = calcArea(grid, hori + 1, vert + 1, m - 1, n - 1);
minSum = Math.min(minSum, top + botLeft + botRight);
}
}

// 5. 竖直分割后，左半部分再水平分割
for (int vert = 0; vert < n - 1; vert++) {
for (int hori = 0; hori < m - 1; hori++) {
int leftTop = calcArea(grid, 0, 0, hori, vert);
int leftBot = calcArea(grid, hori + 1, 0, m - 1, vert);
int right = calcArea(grid, 0, vert + 1, m - 1, n - 1);
minSum = Math.min(minSum, leftTop + leftBot + right);
}
}

// 6. 竖直分割后，右半部分再水平分割
for (int vert = 0; vert < n - 1; vert++) {
for (int hori = 0; hori < m - 1; hori++) {
int left = calcArea(grid, 0, 0, m - 1, vert);
int rightTop = calcArea(grid, 0, vert + 1, hori, n - 1);
int rightBot = calcArea(grid, hori + 1, vert + 1, m - 1, n - 1);
minSum = Math.min(minSum, left + rightTop + rightBot);
}
}

return minSum;
}

// 计算子矩阵 [x1,y1] ~ [x2,y2] 中所有1的最小包围矩形面积，无1则返回0
private int calcArea(int[][] grid, int x1, int y1, int x2, int y2) {
int minX = Integer.MAX_VALUE, maxX = Integer.MIN_VALUE;
int minY = Integer.MAX_VALUE, maxY = Integer.MIN_VALUE;
boolean hasOne = false;
for (int i = x1; i <= x2; i++) {
for (int j = y1; j <= y2; j++) {
if (grid[i][j] == 1) {
hasOne = true;
minX = Math.min(minX, i);
maxX = Math.max(maxX, i);
minY = Math.min(minY, j);
maxY = Math.max(maxY, j);
}
}
}
return hasOne ? (maxX - minX + 1) * (maxY - minY + 1) : 0;
}
}

复杂度分析

- 时间复杂度：O(m^2n + mn^2)，其中 m,n 为矩阵行列数（最大30）。枚举切割线共约 4000 种组合，单次面积计算遍历子矩阵，总运算量在 1e6 级别，Java 可稳定通过。
- 空间复杂度：O(1)，仅使用常数额外空间。

需要我补充前缀和优化版代码（将单次面积计算降为 O(1)），或者添加测试用例验证吗？