![](https://img.shields.io/badge/分数-1348-4051B5?style=flat-square)
题目描述
给你一个二维 二进制 数组 grid
。请你找出一个边在水平方向和竖直方向上、面积 最小 的矩形,并且满足 grid
中所有的 1 都在矩形的内部。
返回这个矩形可能的 最小 面积。
示例 1:
输入: grid = [[0,1,0],[1,0,1]]
输出: 6
解释:
![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/3100-3199/3195.Find%20the%20Minimum%20Area%20to%20Cover%20All%20Ones%20I/images/examplerect0.png)
这个最小矩形的高度为 2,宽度为 3,因此面积为 2 * 3 = 6
。
示例 2:
输入: grid = [[0,0],[1,0]]
输出: 1
解释:
![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/3100-3199/3195.Find%20the%20Minimum%20Area%20to%20Cover%20All%20Ones%20I/images/examplerect1.png)
这个最小矩形的高度和宽度都是 1,因此面积为 1 * 1 = 1
。
提示:
1 <= grid.length, grid[i].length <= 1000
grid[i][j]
是 0 或 1。
- 输入保证
grid
中至少有一个 1 。
解法
方法一:求最小边界和最大边界
我们可以遍历 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)$,其中 $m$ 和 $n$ 分别是 grid
的行数和列数。空间复杂度 $O(1)$。
1
2
3
4
5
6
7
8
9
10
11
12 | 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)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution {
public int minimumArea(int[][] grid) {
int m = grid.length, n = grid[0].length;
int x1 = m, y1 = n;
int x2 = 0, y2 = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
x1 = Math.min(x1, i);
y1 = Math.min(y1, j);
x2 = Math.max(x2, i);
y2 = Math.max(y2, j);
}
}
}
return (x2 - x1 + 1) * (y2 - y1 + 1);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution {
public:
int minimumArea(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int x1 = m, y1 = n;
int x2 = 0, y2 = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
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);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13 | func minimumArea(grid [][]int) int {
x1, y1 := len(grid), len(grid[0])
x2, y2 := 0, 0
for i, row := range grid {
for j, x := range row {
if x == 1 {
x1, y1 = min(x1, i), min(y1, j)
x2, y2 = max(x2, i), max(y2, j)
}
}
}
return (x2 - x1 + 1) * (y2 - y1 + 1)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | function minimumArea(grid: number[][]): number {
const [m, n] = [grid.length, grid[0].length];
let [x1, y1] = [m, n];
let [x2, y2] = [0, 0];
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] === 1) {
x1 = Math.min(x1, i);
y1 = Math.min(y1, j);
x2 = Math.max(x2, i);
y2 = Math.max(y2, j);
}
}
}
return (x2 - x1 + 1) * (y2 - y1 + 1);
}
|