2025-01-25：包含所有 1 的最小矩形面积Ⅰ。用go语言，给定一个二维的二进制数组 grid，任务是找到一个矩形，该矩形的边缘与水平和垂直方向对齐，并且其面积最小，且矩形内部必须包含所有的 1。

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

1 <= grid.length, grid[i].length <= 1000。

grid[i][j] 是 0 或 1。

输入保证 grid 中至少有一个 1 。

输入： grid = [[0,1,0],[1,0,1]]。

输出： 6。

解释：

这个最小矩形的高度为 2，宽度为 3，因此面积为 2 * 3 = 6。

答案2025-01-25：

chatgpt

题目来自leetcode3195。

大体步骤如下：

1.初始化左边界 left 为 grid[0] 的长度，右边界 right 为 0，顶部边界 top 为 grid 的长度，底部边界 bottom 为 0。

2.遍历二维数组 grid，对于每个元素：

2.1.如果当前元素是1，更新左边界、右边界、顶部边界和底部边界：

2.1.1.更新左边界为当前位置列数 j 与当前左边界 left 的最小值。

2.1.2.更新右边界为当前位置列数 j 与当前右边界 right 的最大值。

2.1.3.更新顶部边界为当前位置行数 i 与当前顶部边界 top 的最小值。

2.1.4.更新底部边界为当前位置行数 i。

3.计算矩形的面积:

• 矩形的宽度是 (right - left + 1)，高度是 (bottom - top + 1)。

• 最小矩形面积即为宽度乘以高度，即 (right - left + 1) * (bottom - top + 1)。

总的时间复杂度为 $O(M \times N)$，其中 M 为二维数组的行数，N 为二维数组的列数。

额外空间复杂度为 O(1)，只使用了常数级额外空间来存储边界值。

Go完整代码如下：

package main

import (
	"fmt"
)

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)
}

func main() {
	grid := [][]int{{0,1,0},{1,0,1}}
	result := minimumArea(grid)
	fmt.Println(result)
}

Rust完整代码如下：

fn minimum_area(grid: Vec<Vec<i32>>) -> i32 {
    let mut left = grid[0].len() as i32;
    let mut right = 0;
    let mut top = grid.len() as i32;
    let mut bottom = 0;

    for (i, row) in grid.iter().enumerate() {
        for (j, &x) in row.iter().enumerate() {
            if x == 1 {
                left = left.min(j as i32);
                right = right.max(j as i32);
                top = top.min(i as i32);
                bottom = i as i32;
            }
        }
    }

    (right - left + 1) * (bottom - top + 1) as i32
}

fn main() {
    let grid = vec![vec![0, 1, 0], vec![1, 0, 1]];
    let result = minimum_area(grid);
    println!("{}", result);
}

Python完整代码如下：

# -*-coding:utf-8-*-

def minimum_area(grid):
    left, right = len(grid[0]), 0
    top, bottom = len(grid), 0
    
    for i in range(len(grid)):
        for j in range(len(grid[i])):
            if grid[i][j] == 1:
                left = min(left, j)
                right = max(right, j)
                top = min(top, i)
                bottom = i
    
    return (right - left + 1) * (bottom - top + 1)

def main():
    grid = [[0, 1, 0], [1, 0, 1]]
    result = minimum_area(grid)
    print(result)

if __name__ == "__main__":
    main()

Solidity完整代码如下：

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

contract MinimumArea {
    function minimumArea(uint[][] memory grid) public pure returns (uint) {
        uint left = grid[0].length;
        uint right = 0;
        uint top = grid.length;
        uint bottom = 0;

        for (uint i = 0; i < grid.length; i++) {
            for (uint j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    if (j < left) {
                        left = j;
                    }
                    if (j > right) {
                        right = j;
                    }
                    if (i < top) {
                        top = i;
                    }
                    bottom = i;
                }
            }
        }

        return (right - left + 1) * (bottom - top + 1);
    }
}