长方形题库

最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例1:

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。

示例2:

输入：matrix = []
输出：0

方案 动态规划

思路:

1. 状态定义: dp[i][j]为矩阵第i行第j列元素的左边连续1的数量
2. 状态转移方程: 当考虑matrix[i][j]为右下角的矩形时，我们枚举0<=k<=i的所有可能的k

• 0<=k<=i 行中，最大宽度为min(dp[i][j],dp[i-1][j],……,dp[k][j])
• 0<=k<=i 行中，最大面积为i-k+1*最大宽度

3. 初始化状态:

• dp 初始为 0
• 如果matrix[i][j]=1时:
  • 如果j==0,则方程为dp[i][j]=0+1
  • 如果j!=0,则方程为dp[i][j]=dp[i][j-1]+1

4. 问题答案: matrix[i][j]中，0<=k<=i

• 高度: i-k+1
• 宽度: dp[k][j]
• 面积: 宽度*高度
• 答案: 面积中的最大值

:::details 点击查看代码

function maximalRectangle(matrix) {
    const row=matrix.length;
    if(row==0){
        return 0;
    }
    const col=matrix[0].length;
    const dp=new Array(row).fill(0).map(()=>new Array(col).fill(0))
    for(let i=0;i<row;i++){
        for(let j=0;j<col;j++){
            if(matrix[i][j]==1){
                dp[i][j]=(j==0?0:dp[i][j-1])+1;
            }
        }
    }
    let result=0;
    for(let i=0;i<row;i++){
        for(let j=0;j<col;j++){
            if(matrix[i][j]==0){
                continue;
            }
            let width=dp[i][j];
            let area=width;
            for(let k=i-1;k>=0;k--){
                width=Math.min(width,dp[k][j]);
                area=Math.max(area,(i-k+1)*width);
            }
            result=Math.max(result,area);
        }
    }
    return result;
};

:::

性能分析:

• 时间复杂度: O(m^2*n)
• 空间复杂度: O(m*n)

矩形区域不超过 K 的最大数值和

给你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。

题目数据保证总会存在一个数值和不超过 k 的矩形区域。

示例1:

输入：matrix = [[1,0,1],[0,-2,3]], k = 2
输出：2
解释：蓝色边框圈出来的矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。

示例2:

输入：matrix = [[2,2,-1]], k = 3
输出：3

方案 前缀和与二分

思路:

• 枚举矩形的上下边界，并计算出该边界内每列的元素和，则原问题转换成了如下一维问题：给定一个整数数组和一个整数 k，计算该数组的最大区间和，要求区间和不超过 k

:::details 点击查看代码

function sumSetMin(set,k){
    let min=Infinity;
    for(let item of set){
        if(item>=k&&item<min){
            min=item;
        }
    }
    return min==Infinity?null:min;
}
function maxSumSubmatrix(matrix, k) {
    let row=matrix.length;
    let col=matrix[0].length;
    let result=-Infinity;
    for(let i=0;i<row;i++){
        let sum=new Array(col).fill(0);
        for(let j=i;j<row;j++){
            for(let c=0;c<col;c++){
                sum[c]+=matrix[j][c];
            }
            let sumSet=new Set();
            sumSet.add(0);
            let temp=0;
            for(let item of sum){
                temp+=item;
                let min=sumSetMin(sumSet,temp-k);
                if(min!=null){
                    result=Math.max(result,temp-min);
                }
                sumSet.add(temp);
            }
        }
    }
    return result;
};

:::

性能分析: