Medium

题目描述

给你一个二维二进制数组 grid。你需要找到一个具有水平和垂直边的矩形，使其面积最小，且 grid 中的所有 1 都在这个矩形内。

返回矩形的最小可能面积。

示例 1：

输入：grid = [[0,1,0],[1,0,1]]
输出：6
解释：
最小矩形的高度为 2，宽度为 3，所以面积为 2 * 3 = 6。

示例 2：

输入：grid = [[1,0],[0,0]]
输出：1
解释：
最小矩形的高度和宽度都为 1，所以面积为 1 * 1 = 1。

约束条件：

  • 1 <= grid.length, grid[i].length <= 1000
  • grid[i][j] 要么是 0，要么是 1
  • 输入保证 grid 中至少有一个 1

提示：

  • 在两个方向上找到值为 1 的单元格的最小和最大坐标。

解题思路

这道题目要求找到能覆盖所有1的最小矩形面积。核心思路是找到所有1的边界坐标。

解题思路：

要形成最小的矩形，我们需要找到包含所有1的最小边界框。具体来说，需要找到：

  • 包含1的最小行索引（top）
  • 包含1的最大行索引（bottom）
  • 包含1的最小列索引（left）
  • 包含1的最大列索引（right）

然后矩形的高度为 bottom - top + 1，宽度为 right - left + 1，面积即为高度乘以宽度。

算法步骤：

  1. 遍历整个网格，记录所有1的位置
  2. 找到1所在的最小/最大行和列坐标
  3. 计算矩形的高度和宽度
  4. 返回面积

时间复杂度： O(m×n)，其中m是行数，n是列数 空间复杂度： O(1)，只使用常数额外空间

这是一个直观且高效的解法，通过一次遍历即可找到边界并计算出结果。

代码实现

class Solution {
public:
    int minimumArea(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int top = m, bottom = -1, left = n, right = -1;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    top = min(top, i);
                    bottom = max(bottom, i);
                    left = min(left, j);
                    right = max(right, j);
                }
            }
        }
        
        return (bottom - top + 1) * (right - left + 1);
    }
};

class Solution:
    def minimumArea(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        top, bottom, left, right = m, -1, n, -1
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    top = min(top, i)
                    bottom = max(bottom, i)
                    left = min(left, j)
                    right = max(right, j)
        
        return (bottom - top + 1) * (right - left + 1)

public class Solution {
    public int MinimumArea(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        int top = m, bottom = -1, left = n, right = -1;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    top = Math.Min(top, i);
                    bottom = Math.Max(bottom, i);
                    left = Math.Min(left, j);
                    right = Math.Max(right, j);
                }
            }
        }
        
        return (bottom - top + 1) * (right - left + 1);
    }
}

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minimumArea = function(grid) {
    let minRow = grid.length, maxRow = -1;
    let minCol = grid[0].length, maxCol = -1;
    
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (grid[i][j] === 1) {
                minRow = Math.min(minRow, i);
                maxRow = Math.max(maxRow, i);
                minCol = Math.min(minCol, j);
                maxCol = Math.max(maxCol, j);
            }
        }
    }
    
    return (maxRow - minRow + 1) * (maxCol - minCol + 1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m×n)需要遍历整个网格一次，其中m是行数，n是列数
空间复杂度O(1)只使用常数个变量存储边界坐标

相关题目