题目大意给定一个二维二进制矩阵用 3 个互不重叠、面积非零 的轴对齐矩形覆盖矩阵中所有的 1矩形可以相接但不能重叠求三个矩形的面积之和的最小值。数据范围矩阵行列数均不超过 30。核心思路所有合法的三矩形不重叠布局都可以归为以下 6 类切割模式只需枚举所有切割线的位置计算每种模式下的最小面积和最终取全局最小值即可1. 两条水平切割线将矩阵分为上、中、下三部分2. 两条竖直切割线将矩阵分为左、中、右三部分3. 一条水平切割线分为上下上半部分再用一条竖直切割线拆分4. 一条水平切割线分为上下下半部分再用一条竖直切割线拆分5. 一条竖直切割线分为左右左半部分再用一条水平切割线拆分6. 一条竖直切割线分为左右右半部分再用一条水平切割线拆分对每个切割后的子区域计算其内部所有 1 的最小包围矩形面积求和后更新最小值。Java 完整实现javaclass 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则返回0private 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)或者添加测试用例验证吗
豆包 LeetCode 3197. 包含所有 1 的最小矩形面积 II Java实现
题目大意给定一个二维二进制矩阵用 3 个互不重叠、面积非零 的轴对齐矩形覆盖矩阵中所有的 1矩形可以相接但不能重叠求三个矩形的面积之和的最小值。数据范围矩阵行列数均不超过 30。核心思路所有合法的三矩形不重叠布局都可以归为以下 6 类切割模式只需枚举所有切割线的位置计算每种模式下的最小面积和最终取全局最小值即可1. 两条水平切割线将矩阵分为上、中、下三部分2. 两条竖直切割线将矩阵分为左、中、右三部分3. 一条水平切割线分为上下上半部分再用一条竖直切割线拆分4. 一条水平切割线分为上下下半部分再用一条竖直切割线拆分5. 一条竖直切割线分为左右左半部分再用一条水平切割线拆分6. 一条竖直切割线分为左右右半部分再用一条水平切割线拆分对每个切割后的子区域计算其内部所有 1 的最小包围矩形面积求和后更新最小值。Java 完整实现javaclass 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则返回0private 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)或者添加测试用例验证吗
