3197. 覆盖所有一的最小矩形面积 II

Hard

题目描述

给你一个二维二进制数组 grid。你需要找到 3 个不重叠的非零面积矩形，这些矩形的边都是水平和垂直的，使得 grid 中所有的 1 都在这些矩形内。

返回这些矩形面积的最小可能总和。

注意，矩形允许相邻。

示例 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 的矩形覆盖。

示例 2:

输入: grid = [[1,0,1,0],[0,1,0,1]]
输出: 5
解释:
- 位置 (0, 0) 和 (0, 2) 的 1 被面积为 3 的矩形覆盖。
- 位置 (1, 1) 的 1 被面积为 1 的矩形覆盖。
- 位置 (1, 3) 的 1 被面积为 1 的矩形覆盖。

约束条件:

1 <= grid.length, grid[i].length <= 30
grid[i][j] 为 0 或 1
输入保证 grid 中至少有三个 1

解题思路

这是一个分割问题，需要用3个矩形覆盖所有的1。根据题目提示，我们可以采用分而治之的策略。

解题思路：

由于需要3个不重叠的矩形，我们可以考虑以下几种分割方式：

水平分割：先用一个矩形覆盖上部分，剩下区域用两个矩形覆盖
水平分割：先用一个矩形覆盖下部分，剩下区域用两个矩形覆盖
垂直分割：先用一个矩形覆盖左部分，剩下区域用两个矩形覆盖
垂直分割：先用一个矩形覆盖右部分，剩下区域用两个矩形覆盖

对于每种分割方式，剩余区域需要用两个矩形覆盖，这又可以通过水平或垂直分割实现。

关键函数：

getArea()：计算覆盖指定区域内所有1的最小矩形面积
minAreaWith2Rectangles()：用两个矩形覆盖指定区域的最小面积

算法流程：

预处理：找到所有1的位置
枚举所有可能的分割线
对每种分割方式计算总面积
返回最小值

时间复杂度主要来自于枚举分割线和计算每个区域的最小矩形面积。

代码实现

class Solution {
public:
    int minimumSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        
        // Helper function to get minimum area of one rectangle covering all 1s in a region
        auto getArea = [&](int r1, int c1, int r2, int c2) -> int {
            int minR = m, maxR = -1, minC = n, maxC = -1;
            for (int i = r1; i <= r2; i++) {
                for (int j = c1; j <= c2; j++) {
                    if (grid[i][j] == 1) {
                        minR = min(minR, i);
                        maxR = max(maxR, i);
                        minC = min(minC, j);
                        maxC = max(maxC, j);
                    }
                }
            }
            if (minR == m) return 0; // No 1s found
            return (maxR - minR + 1) * (maxC - minC + 1);
        };
        
        // Helper function to get minimum area using 2 rectangles
        auto minAreaWith2Rectangles = [&](int r1, int c1, int r2, int c2) -> int {
            int result = INT_MAX;
            
            // Try horizontal split
            for (int row = r1; row < r2; row++) {
                int area1 = getArea(r1, c1, row, c2);
                int area2 = getArea(row + 1, c1, r2, c2);
                if (area1 > 0 && area2 > 0) {
                    result = min(result, area1 + area2);
                }
            }
            
            // Try vertical split
            for (int col = c1; col < c2; col++) {
                int area1 = getArea(r1, c1, r2, col);
                int area2 = getArea(r1, col + 1, r2, c2);
                if (area1 > 0 && area2 > 0) {
                    result = min(result, area1 + area2);
                }
            }
            
            return result;
        };
        
        int result = INT_MAX;
        
        // Case 1: Top rectangle + bottom 2 rectangles
        for (int row = 0; row < m - 1; row++) {
            int topArea = getArea(0, 0, row, n - 1);
            int bottomArea = minAreaWith2Rectangles(row + 1, 0, m - 1, n - 1);
            if (topArea > 0 && bottomArea < INT_MAX) {
                result = min(result, topArea + bottomArea);
            }
        }
        
        // Case 2: Bottom rectangle + top 2 rectangles
        for (int row = 1; row < m; row++) {
            int bottomArea = getArea(row, 0, m - 1, n - 1);
            int topArea = minAreaWith2Rectangles(0, 0, row - 1, n - 1);
            if (bottomArea > 0 && topArea < INT_MAX) {
                result = min(result, topArea + bottomArea);
            }
        }
        
        // Case 3: Left rectangle + right 2 rectangles
        for (int col = 0; col < n - 1; col++) {
            int leftArea = getArea(0, 0, m - 1, col);
            int rightArea = minAreaWith2Rectangles(0, col + 1, m - 1, n - 1);
            if (leftArea > 0 && rightArea < INT_MAX) {
                result = min(result, leftArea + rightArea);
            }
        }
        
        // Case 4: Right rectangle + left 2 rectangles
        for (int col = 1; col < n; col++) {
            int rightArea = getArea(0, col, m - 1, n - 1);
            int leftArea = minAreaWith2Rectangles(0, 0, m - 1, col - 1);
            if (rightArea > 0 && leftArea < INT_MAX) {
                result = min(result, leftArea + rightArea);
            }
        }
        
        return result;
    }
};

class Solution:
    def minimumSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        def get_area(r1, c1, r2, c2):
            min_r, max_r = m, -1
            min_c, max_c = n, -1
            
            for i in range(r1, r2 + 1):
                for j in range(c1, c2 + 1):
                    if grid[i][j] == 1:
                        min_r = min(min_r, i)
                        max_r = max(max_r, i)
                        min_c = min(min_c, j)
                        max_c = max(max_c, j)
            
            if min_r == m:  # No 1s found
                return 0
            return (max_r - min_r + 1) * (max_c - min_c + 1)
        
        def min_area_with_2_rectangles(r1, c1, r2, c2):
            result = float('inf')
            
            # Try horizontal split
            for row in range(r1, r2):
                area1 = get_area(r1, c1, row, c2)
                area2 = get_area(row + 1, c1, r2, c2)
                if area1 > 0 and area2 > 0:
                    result = min(result, area1 + area2)
            
            # Try vertical split
            for col in range(c1, c2):
                area1 = get_area(r1, c1, r2, col)
                area2 = get_area(r1, col + 1, r2, c2)
                if area1 > 0 and area2 > 0:
                    result = min(result, area1 + area2)
            
            return result
        
        result = float('inf')
        
        # Case 1: Top rectangle + bottom 2 rectangles
        for row in range(m - 1):
            top_area = get_area(0, 0, row, n - 1)
            bottom_area = min_area_with_2_rectangles(row + 1, 0, m - 1, n - 1)
            if top_area > 0 and bottom_area < float('inf'):
                result = min(result, top_area + bottom_area)
        
        # Case 2: Bottom rectangle + top 2 rectangles
        for row in range(1, m):
            bottom_area = get_area(row, 0, m - 1, n - 1)
            top_area = min_area_with_2_rectangles(0, 0, row - 1, n - 1)
            if bottom_area > 0 and top_area < float('inf'):
                result = min(result, top_area + bottom_area)
        
        # Case 3: Left rectangle + right 2 rectangles
        for col in range(n - 1):
            left_area = get_area(0, 0, m - 1, col)
            right_area = min_area_with_2_rectangles(0, col + 1, m - 1, n - 1)
            if left_area > 0 and right_area < float('inf'):
                result = min(result, left_area + right_area)
        
        # Case 4: Right rectangle + left 2 rectangles
        for col in range(1, n):
            right_area = get_area(0, col, m - 1, n - 1)
            left_area = min_area_with_2_rectangles(0, 0, m - 1, col - 1)
            if right_area > 0 and left_area < float('inf'):
                result = min(result, left_area + right_area)
        
        return result

public class Solution {
    public int MinimumSum(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        
        int GetArea(int r1, int c1, int r2, int c2) {
            int minR = m, maxR = -1, minC = n, maxC = -1;
            
            for (int i = r1; i <= r2; i++) {
                for (int j = c1; j <= c2; j++) {
                    if (grid[i][j] == 1) {
                        minR = Math.Min(minR, i);
                        maxR = Math.Max(maxR, i);
                        minC = Math.Min(minC, j);
                        maxC = Math.Max(maxC, j);
                    }
                }
            }
            
            if (minR == m) return 0;
            return (maxR - minR + 1) * (maxC - minC + 1);
        }
        
        int MinAreaWith2Rectangles(int r1, int c1, int r2, int c2) {
            int result = int.MaxValue;
            
            // Try horizontal split
            for (int row = r1; row < r2; row++) {
                int area1 = GetArea(r1, c1, row, c2);
                int area2 = GetArea(row + 1, c1, r2, c2);
                if (area1 > 0 && area2 > 0) {
                    result = Math.Min(result, area1 + area2);
                }
            }
            
            // Try vertical split
            for (int col = c1; col < c2; col++) {
                int area1 = GetArea(r1, c1, r2, col);
                int area2 = GetArea(r1, col + 1, r2, c2);
                if (area1 > 0 && area2 > 0) {
                    result = Math.Min(result, area1 + area2);
                }
            }
            
            return result;
        }
        
        int result = int.MaxValue;
        
        // Case 1: Top rectangle + bottom 2 rectangles
        for (int row = 0; row < m - 1; row++) {
            int topArea = GetArea(0, 0, row, n - 1);
            int bottomArea = MinAreaWith2Rectangles(row + 1, 0, m - 1, n - 1);
            if (topArea > 0 && bottomArea < int.MaxValue) {
                result = Math.Min(result, topArea + bottomArea);
            }
        }
        
        // Case 2: Bottom rectangle + top 2 rectangles
        for (int row = 1; row < m; row++) {
            int bottomArea = GetArea(row, 0, m - 1, n - 1);
            int topArea = MinAreaWith2Rectangles(0, 0, row - 1, n - 1);
            if (bottomArea > 0 && topArea < int.MaxValue) {
                result = Math.Min(result, topArea + bottomArea);
            }
        }
        
        // Case 3: Left rectangle + right 2 rectangles
        for (int col = 0; col < n - 1; col++) {
            int leftArea = GetArea(0, 0, m - 1, col);
            int rightArea = MinAreaWith2Rectangles(0, col + 1, m - 1, n - 1);
            if (leftArea > 0 && rightArea < int.MaxValue) {
                result = Math.Min(result, leftArea + rightArea);
            }
        }
        
        // Case 4: Right rectangle + left 2 rectangles
        for (int col = 1; col < n; col++) {
            int rightArea = GetArea(0, col, m - 1, n - 1);
            int leftArea = MinAreaWith2Rectangles(0, 0, m - 1, col - 1);
            if (rightArea > 0 && leftArea < int.MaxValue) {
                result = Math.Min(result, leftArea + rightArea);
            }
        }
        
        return result;
    }
}

var minimumSum = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    
    function getArea(r1, c1, r2, c2) {
        return (r2 - r1 + 1) * (c2 - c1 + 1);
    }
    
    function getBounds(r1, c1, r2, c2) {
        let minR = m, maxR = -1, minC = n, maxC = -1;
        for (let i = r1; i <= r2; i++) {
            for (let j = c1; j <= c2; j++) {
                if (grid[i][j] === 1) {
                    minR = Math.min(minR, i);
                    maxR = Math.max(maxR, i);
                    minC = Math.min(minC, j);
                    maxC = Math.max(maxC, j);
                }
            }
        }
        if (minR === m) return 0;
        return getArea(minR, minC, maxR, maxC);
    }
    
    let ans = Infinity;
    
    // Horizontal splits
    for (let i1 = 0; i1 < m - 2; i1++) {
        for (let i2 = i1 + 1; i2 < m - 1; i2++) {
            let area1 = getBounds(0, 0, i1, n - 1);
            let area2 = getBounds(i1 + 1, 0, i2, n - 1);
            let area3 = getBounds(i2 + 1, 0, m - 1, n - 1);
            if (area1 > 0 && area2 > 0 && area3 > 0) {
                ans = Math.min(ans, area1 + area2 + area3);
            }
        }
    }
    
    // Vertical splits
    for (let j1 = 0; j1 < n - 2; j1++) {
        for (let j2 = j1 + 1; j2 < n - 1; j2++) {
            let area1 = getBounds(0, 0, m - 1, j1);
            let area2 = getBounds(0, j1 + 1, m - 1, j2);
            let area3 = getBounds(0, j2 + 1, m - 1, n - 1);
            if (area1 > 0 && area2 > 0 && area3 > 0) {
                ans = Math.min(ans, area1 + area2 + area3);
            }
        }
    }
    
    // One horizontal, one vertical split (4 patterns)
    for (let i = 0; i < m - 1; i++) {
        for (let j = 0; j < n - 1; j++) {
            // Top-left, top-right, bottom
            let area1 = getBounds(0, 0, i, j);
            let area2 = getBounds(0, j + 1, i, n - 1);
            let area3 = getBounds(i + 1, 0, m - 1, n - 1);
            if (area1 > 0 && area2 > 0 && area3 > 0) {
                ans = Math.min(ans, area1 + area2 + area3);
            }
            
            // Top, bottom-left, bottom-right
            area1 = getBounds(0, 0, i, n - 1);
            area2 = getBounds(i + 1, 0, m - 1, j);
            area3 = getBounds(i + 1, j + 1, m - 1, n - 1);
            if (area1 > 0 && area2 > 0 && area3 > 0) {
                ans = Math.min(ans, area1 + area2 + area3);
            }
            
            // Left, right-top, right-bottom
            area1 = getBounds(0, 0, m - 1, j);
            area2 = getBounds(0, j + 1, i, n - 1);
            area3 = getBounds(i + 1, j + 1, m - 1, n - 1);
            if (area1 > 0 && area2 > 0 && area3 > 0) {
                ans = Math.min(ans, area1 + area2 + area3);
            }
            
            // Left-top, left-bottom, right
            area1 = getBounds(0, 0, i, j);
            area2 = getBounds(i + 1, 0, m - 1, j);
            area3 = getBounds(0, j + 1, m - 1, n - 1);
            if (area1 > 0 && area2 > 0 && area3 > 0) {
                ans = Math.min(ans, area1 + area2 + area3);
            }
        }
    }
    
    return ans;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(m³n³)	枚举分割线需要O(m+n)，每次计算区域面积需要O(mn)，总共需要计算O(mn)次
空间复杂度	O(1)	只使用常数额外空间

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目