2025-01-27：包含所有 1 的最小矩形面积Ⅱ。用go语言，给定一个二维二进制数组，找到三个非重叠且面积非零的矩形，这三个矩形在水平和垂直方向上覆盖了数组中的所有1，返回这三个矩形的面积之和的最小值。这些矩形可以相互接触。

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

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

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

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

输出： 5。

解释：

位于 (0, 0) 和 (1, 0) 的 1 被一个面积为 2 的矩形覆盖。

位于 (0, 2) 和 (1, 2) 的 1 被一个面积为 2 的矩形覆盖。

位于 (1, 1) 的 1 被一个面积为 1 的矩形覆盖。

答案2025-01-27：

chatgpt

题目来自leetcode3197。

大体步骤如下：

Go完整代码如下：

package main

import (
	"fmt"
	"math"
)

func minimumArea(a [][]int) [][]int {
	m, n := len(a), len(a[0])
	// f[i+1][j+1] 表示包含【左上角为 (0,0) 右下角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
	f := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	type data struct{ top, left, right int }
	border := make([]data, n)
	for j := range border {
		border[j].top = -1 // 无
	}

	for i, row := range a {
		left, right := -1, 0
		for j, x := range row {
			if x > 0 {
				if left < 0 {
					left = j
				}
				right = j
			}
			preB := border[j]
			if left < 0 { // 这一排目前全是 0
				f[i+1][j+1] = f[i][j+1] // 等于上面的结果
			} else if preB.top < 0 { // 这一排有 1，上面全是 0
				f[i+1][j+1] = right - left + 1
				border[j] = data{i, left, right}
			} else { // 这一排有 1，上面也有 1
				l, r := min(preB.left, left), max(preB.right, right)
				f[i+1][j+1] = (r - l + 1) * (i - preB.top + 1)
				border[j] = data{preB.top, l, r}
			}
		}
	}
	return f
}

func minimumSum(grid [][]int) int {
	ans := math.MaxInt
	f := func(a [][]int) {
		m, n := len(a), len(a[0])
		type pair struct{ l, r int }
		lr := make([]pair, m) // 每一行最左最右 1 的列号
		for i, row := range a {
			l, r := -1, 0
			for j, x := range row {
				if x > 0 {
					if l < 0 {
						l = j
					}
					r = j
				}
			}
			lr[i] = pair{l, r}
		}

		// lt[i+1][j+1] = 包含【左上角为 (0,0) 右下角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
		lt := minimumArea(a)
		a = rotate(a)
		// lb[i][j+1] = 包含【左下角为 (m-1,0) 右上角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
		lb := rotate(rotate(rotate(minimumArea(a))))
		a = rotate(a)
		// rb[i][j] = 包含【右下角为 (m-1,n-1) 左上角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
		rb := rotate(rotate(minimumArea(a)))
		a = rotate(a)
		// rt[i+1][j] = 包含【右上角为 (0,n-1) 左下角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
		rt := rotate(minimumArea(a))

		if m >= 3 {
			for i := 1; i < m; i++ {
				left, right, top, bottom := n, 0, m, 0
				for j := i + 1; j < m; j++ {
					if p := lr[j-1]; p.l >= 0 {
						left = min(left, p.l)
						right = max(right, p.r)
						top = min(top, j-1)
						bottom = j - 1
					}
					// 图片上左
					area := lt[i][n] // minimumArea(a[:i], 0, n)
					area += (right - left + 1) * (bottom - top + 1) // minimumArea(a[i:j], 0, n)
					area += lb[j][n] // minimumArea(a[j:], 0, n)
					ans = min(ans, area)
				}
			}
		}

		if m >= 2 && n >= 2 {
			for i := 1; i < m; i++ {
				for j := 1; j < n; j++ {
					// 图片上中
					area := lt[i][n] // minimumArea(a[:i], 0, n)
					area += lb[i][j] // minimumArea(a[i:], 0, j)
					area += rb[i][j] // minimumArea(a[i:], j, n)
					ans = min(ans, area)
					// 图片上右
					area = lt[i][j]  // minimumArea(a[:i], 0, j)
					area += rt[i][j] // minimumArea(a[:i], j, n)
					area += lb[i][n] // minimumArea(a[i:], 0, n)
					ans = min(ans, area)
				}
			}
		}
	}
	f(grid)
	f(rotate(grid))
	return ans
}

// 顺时针旋转矩阵 90°
func rotate(a [][]int) [][]int {
	m, n := len(a), len(a[0])
	b := make([][]int, n)
	for i := range b {
		b[i] = make([]int, m)
	}
	for i, row := range a {
		for j, x := range row {
			b[j][m-1-i] = x
		}
	}
	return b
}

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

Python完整代码如下：

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

import math

def minimum_area(a):
    m, n = len(a), len(a[0])
    # f[i+1][j+1] 表示包含【左上角为 (0,0) 右下角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
    f = [[0] * (n + 1) for _ in range(m + 1)]
    
    border = [{'top': -1, 'left': 0, 'right': 0} for _ in range(n)]

    for i in range(m):
        left, right = -1, 0
        for j in range(n):
            if a[i][j] > 0:
                if left < 0:
                    left = j
                right = j
            
            preB = border[j]
            if left < 0:  # 这一排目前全是 0
                f[i + 1][j + 1] = f[i][j + 1]  # 等于上面的结果
            elif preB['top'] < 0:  # 这一排有 1，上面全是 0
                f[i + 1][j + 1] = right - left + 1
                border[j] = {'top': i, 'left': left, 'right': right}
            else:  # 这一排有 1，上面也有 1
                l = min(preB['left'], left)
                r = max(preB['right'], right)
                f[i + 1][j + 1] = (r - l + 1) * (i - preB['top'] + 1)
                border[j] = {'top': preB['top'], 'left': l, 'right': r}
    return f

def minimum_sum(grid):
    ans = math.inf
    def f(a):
        nonlocal ans
        m, n = len(a), len(a[0])
        lr = [(0, 0)] * m  # 每一行最左最右 1 的列号        
        for i in range(m):
            l, r = -1, 0
            for j in range(n):
                if a[i][j] > 0:
                    if l < 0:
                        l = j
                    r = j
            lr[i] = (l, r)

        lt = minimum_area(a)
        a_rotated = rotate(a)
        lb = rotate(rotate(rotate(minimum_area(a_rotated))))
        a_rotated = rotate(a)
        rb = rotate(rotate(minimum_area(a_rotated)))
        a_rotated = rotate(a)
        rt = rotate(minimum_area(a_rotated))

        if m >= 3:
            for i in range(1, m):
                left, right, top, bottom = n, 0, m, 0
                for j in range(i + 1, m):
                    p = lr[j - 1]
                    if p[0] >= 0:
                        left = min(left, p[0])
                        right = max(right, p[1])
                        top = min(top, j - 1)
                        bottom = j - 1
                    # 图片上左
                    area = lt[i][n]  # minimumArea(a[:i], 0, n)
                    area += (right - left + 1) * (bottom - top + 1)  # minimumArea(a[i:j], 0, n)
                    area += lb[j][n]  # minimumArea(a[j:], 0, n)
                    ans = min(ans, area)

        if m >= 2 and n >= 2:
            for i in range(1, m):
                for j in range(1, n):
                    # 图片上中
                    area = lt[i][n]  # minimumArea(a[:i], 0, n)
                    area += lb[i][j]  # minimumArea(a[i:], 0, j)
                    area += rb[i][j]  # minimumArea(a[i:], j, n)
                    ans = min(ans, area)
                    # 图片上右
                    area = lt[i][j]  # minimumArea(a[:i], 0, j)
                    area += rt[i][j]  # minimumArea(a[:i], j, n)
                    area += lb[i][n]  # minimumArea(a[i:], 0, n)
                    ans = min(ans, area)

    f(grid)
    f(rotate(grid))
    return ans

# 顺时针旋转矩阵 90°
def rotate(a):
    m, n = len(a), len(a[0])
    b = [[0] * m for _ in range(n)]
    for i in range(m):
        for j in range(n):
            b[j][m - 1 - i] = a[i][j]
    return b

if __name__ == "__main__":
    grid = [[1, 0, 1], [1, 1, 1]]
    result = minimum_sum(grid)
    print(result)

Javascript完整代码如下：

function minimumArea(a) {
    const m = a.length;
    const n = a[0].length;
    const f = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    const border = Array.from({ length: n }, () => ({ top: -1, left: 0, right: 0 }));

    for (let i = 0; i < m; i++) {
        const row = a[i];
        let left = -1;
        let right = 0;

        for (let j = 0; j < n; j++) {
            const x = row[j];
            if (x > 0) {
                if (left < 0) {
                    left = j;
                }
                right = j;
            }
            const preB = border[j];

            if (left < 0) { // 当前行全为 0
                f[i + 1][j + 1] = f[i][j + 1]; // 等于上面的结果
            } else if (preB.top < 0) { // 当前行有 1，上面全为 0
                f[i + 1][j + 1] = right - left + 1;
                border[j] = { top: i, left: left, right: right };
            } else { // 当前行有 1，上面也有 1
                const l = Math.min(preB.left, left);
                const r = Math.max(preB.right, right);
                f[i + 1][j + 1] = (r - l + 1) * (i - preB.top + 1);
                border[j] = { top: preB.top, left: l, right: r };
            }
        }
    }
    return f;
}

function minimumSum(grid) {
    let ans = Number.MAX_SAFE_INTEGER;

    const f = (a) => {
        const m = a.length;
        const n = a[0].length;
        const lr = Array.from({ length: m }, () => ({ l: -1, r: 0 }));

        for (let i = 0; i < m; i++) {
            let l = -1;
            let r = 0;

            for (let j = 0; j < n; j++) {
                if (a[i][j] > 0) {
                    if (l < 0) {
                        l = j;
                    }
                    r = j;
                }
            }
            lr[i] = { l: l, r: r };
        }

        const lt = minimumArea(a);
        a = rotate(a);
        const lb = rotate(rotate(rotate(minimumArea(a))));
        a = rotate(a);
        const rb = rotate(rotate(minimumArea(a)));
        a = rotate(a);
        const rt = rotate(minimumArea(a));

        if (m >= 3) {
            for (let i = 1; i < m; i++) {
                let left = n;
                let right = 0;
                let top = m;
                let bottom = 0;

                for (let j = i + 1; j < m; j++) {
                    const p = lr[j - 1];
                    if (p.l >= 0) {
                        left = Math.min(left, p.l);
                        right = Math.max(right, p.r);
                        top = Math.min(top, j - 1);
                        bottom = j - 1;
                    }
                    // 图片上左
                    let area = lt[i][n]; // minimumArea(a[:i], 0, n)
                    area += (right - left + 1) * (bottom - top + 1); // minimumArea(a[i:j], 0, n)
                    area += lb[j][n]; // minimumArea(a[j:], 0, n)
                    ans = Math.min(ans, area);
                }
            }
        }

        if (m >= 2 && n >= 2) {
            for (let i = 1; i < m; i++) {
                for (let j = 1; j < n; j++) {
                    // 图片上中
                    let area = lt[i][n]; // minimumArea(a[:i], 0, n)
                    area += lb[i][j]; // minimumArea(a[i:], 0, j)
                    area += rb[i][j]; // minimumArea(a[i:], j, n)
                    ans = Math.min(ans, area);
                    // 图片上右
                    area = lt[i][j]; // minimumArea(a[:i], 0, j)
                    area += rt[i][j]; // minimumArea(a[:i], j, n)
                    area += lb[i][n]; // minimumArea(a[i:], 0, n)
                    ans = Math.min(ans, area);
                }
            }
        }
    };

    f(grid);
    f(rotate(grid));
    return ans;
}

// 顺时针旋转矩阵 90°
function rotate(a) {
    const m = a.length;
    const n = a[0].length;
    const b = Array.from({ length: n }, () => Array(m).fill(0));

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            b[j][m - 1 - i] = a[i][j];
        }
    }
    return b;
}

// 测试
const grid = [[1, 0, 1], [1, 1, 1]];
const result = minimumSum(grid);
console.log(result);