100334. 包含所有 1 的最小矩形面积 I
给你一个二维 二进制 数组 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 。相似题目
原站题解
golang 解法, 执行用时: 289 ms, 内存消耗: 22.8 MB, 提交时间: 2024-06-27 22:39:29
func minimumArea(grid [][]int) int {
left, right := len(grid[0]), 0
top, bottom := len(grid), 0
for i, row := range grid {
for j, x := range row {
if x == 1 {
left = min(left, j)
right = max(right, j)
top = min(top, i)
bottom = i
}
}
}
return (right - left + 1) * (bottom - top + 1)
}
cpp 解法, 执行用时: 284 ms, 内存消耗: 129.1 MB, 提交时间: 2024-06-27 22:39:11
class Solution {
public:
int minimumArea(vector<vector<int>>& grid) {
int left = grid[0].size(), right = 0, top = grid.size(), bottom = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[i].size(); j++) {
if (grid[i][j]) {
left = min(left, j);
right = max(right, j);
top = min(top, i);
bottom = i;
}
}
}
return (right - left + 1) * (bottom - top + 1);
}
};
java 解法, 执行用时: 6 ms, 内存消耗: 192.7 MB, 提交时间: 2024-06-27 22:38:57
public class Solution {
public int minimumArea(int[][] grid) {
int left = grid[0].length;
int right = 0;
int top = grid.length;
int bottom = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == 1) {
left = Math.min(left, j);
right = Math.max(right, j);
top = Math.min(top, i);
bottom = i;
}
}
}
return (right - left + 1) * (bottom - top + 1);
}
}
python3 解法, 执行用时: 441 ms, 内存消耗: 52.9 MB, 提交时间: 2024-06-27 22:38:43
class Solution:
def minimumArea(self, grid: List[List[int]]) -> int:
left, right = len(grid[0]), 0
top, bottom = len(grid), 0
for i, row in enumerate(grid):
for j, x in enumerate(row):
if x:
left = min(left, j)
right = max(right, j)
top = min(top, i)
bottom = i
return (right - left + 1) * (bottom - top + 1)