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[1]

题目来自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)。

总的时间复杂度为 ，其中 M 为二维数组的行数，N 为二维数组的列数。

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

Go完整代码如下：package mainimport ( "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: MITpragma 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); }}

在这里插入图片描述

引用链接

[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP