长方形题库
最大矩形
给定一个仅包含 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
方案 动态规划
思路:
- 状态定义:
dp[i][j]
为矩阵第i
行第j
列元素的左边连续1
的数量 - 状态转移方程: 当考虑
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
*最大宽度
- 初始化状态:
- dp 初始为 0
- 如果
matrix[i][j]=1
时:- 如果
j==0
,则方程为dp[i][j]=0+1
- 如果
j!=0
,则方程为dp[i][j]=dp[i][j-1]+1
- 如果
- 问题答案:
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;
};
:::
性能分析: