3195.包含所有 1 的最小矩形面积 I：简单题-求长方形四个范围

【LetMeFly】3195.包含所有 1 的最小矩形面积 I：简单题-求长方形四个范围

力扣题目链接：https://leetcode.cn/problems/find-the-minimum-area-to-cover-all-ones-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 。

解题方法：遍历求长方形位置

一个横平竖直的长方形把所有的1覆盖掉，那么我们只需要遍历一次grid，求出所有1中最小的横坐标、最大的横坐标、最小的纵坐标、最大的纵坐标，即为长方形的left、right、up、down，$(r - l + 1) \times (d - u + 1)$即为所求。

• 时间复杂度$O(size(grid))$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-08-22 21:18:33
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-08-22 21:21:31
 */
class Solution {
public:
    int minimumArea(vector<vector<int>>& grid) {
        int l = 1000, r = 0, u = 1000, d = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[i].size(); j++) {
                if (grid[i][j]) {
                    l = min(l, j);
                    r = max(r, j);
                    u = min(u, i);
                    d = max(d, i);
                }
            }
        }
        return (r - l + 1) * (d - u + 1);
    }
};

Python

'''
Author: LetMeFly
Date: 2025-08-22 21:18:33
LastEditors: LetMeFly.xyz
LastEditTime: 2025-08-22 21:23:44
'''
from typing import List

class Solution:
    def minimumArea(self, grid: List[List[int]]) -> int:
        l = u = 1000
        r = d = 0
        for i, line in enumerate(grid):
            for j, g in enumerate(line):
                if g:
                    l = min(l, j)
                    r = max(r, j)
                    u = min(u, i)
                    d = max(d, i)
        return (r - l + 1) * (d - u + 1)

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-08-22 21:18:33
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-08-22 21:33:05
 */
class Solution {
    public int minimumArea(int[][] grid) {
        int l = 1000, r = 0, u = 1000, d = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    l = Math.min(l, j);
                    r = Math.max(r, j);
                    u = Math.min(u, i);
                    d = Math.max(d, i);
                }
            }
        }
        return (r - l + 1) * (d - u + 1);
    }
}

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-08-22 21:18:33
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-08-22 21:30:00
 */
package main

func minimumArea(grid [][]int) int {
    l, r, u, d := 1000, 0, 1000, 0
    for i, row := range grid {
        for j, g := range row {
            if g == 1 {
                l = min(l, j)
                r = max(r, j)
                u = min(u, i)
                d = max(d, i)
            }
        }
    }
    return (r - l + 1) * (d - u + 1)
}

golang第一次提交leetcode出bug了

Rust

/*
 * @Author: LetMeFly
 * @Date: 2025-08-22 21:18:33
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-08-22 21:28:08
 */
impl Solution {
    pub fn minimum_area(grid: Vec<Vec<i32>>) -> i32 {
        let mut l: usize = 1000;
        let mut r: usize = 0;
        let mut u: usize = 1000;
        let mut d: usize = 0;
        for (i, row) in grid.into_iter().enumerate() {
            for (j, g) in row.into_iter().enumerate() {
                if g == 1 {
                    l = l.min(j);
                    r = r.max(j);
                    u = u.min(i);
                    d = d.max(i);
                }
            }
        }
        ((r - l + 1) * (d - u + 1)) as i32
    }
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源