跳转至

3195. 包含所有 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 <= 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);
}

评论