1.题目基本信息
1.1.题目描述
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。
1.2.题目地址
https://leetcode.cn/problems/maximal-rectangle/description
2.解题方法
2.1.解题思路
动态规划+单调栈,可以参考Leetcode 84. 柱状图中最大的矩形
2.2.解题步骤
第一步,边界值判断
第二步,构建left矩阵,left[i][j]为matrix[i][j]处向左连续为1的个数(包括本身)
第三步,遍历每一列,使用最大矩阵的方法求每一列的各个元素能组成的最大矩阵的面积。对于每一列的遍历,目标是构建up和down两个数组,up[i]为j列的i处上面的第一个小于left[i][j]的行索引,down指i处下面的第一个小于left[i][j]的行索引,其中-1和rows相当于链表中的哑结点。中间使用单调栈工具,将与i处相邻且大于left[i][j]的元素pop掉,最后栈顶元素即为目标值。对于down,pop的元素对应的索引处的值一定是i,可以用反证法进行证明。构建每列的up和down后,遍历计算面积最大值即可
第四步,返回结果
3.解题代码
Python代码
class Solution:
# 动态规划+单调栈
def maximalRectangle(self, matrix: List[List[str]]) -> int:
# 第一步,边界值判断
if len(matrix)==0:
return 0
rows,cols=len(matrix),len(matrix[0])
# 第二步,构建left矩阵,left[i][j]为matrix[i][j]处向左连续为1的个数(包括本身)
left=[[0]*cols for _ in range(rows)]
for i in range(rows):
for j in range(cols):
if matrix[i][j]=='1':
left[i][j]=left[i][j-1]+1 if j!=0 else 1
# print("left",left)
# 第三步,遍历每一列,使用最大矩阵的方法求每一列的各个元素能组成的最大矩阵的面积。对于每一列的遍历,目标是构建up和down两个数组,up[i]为j列的i处上面的第一个小于left[i][j]的行索引,down指i处下面的第一个小于left[i][j]的行索引,其中-1和rows相当于链表中的哑结点。中间使用单调栈工具,将与i处相邻且大于left[i][j]的元素pop掉,最后栈顶元素即为目标值。对于down,pop的元素对应的索引处的值一定是i,可以用反证法进行证明。构建每列的up和down后,遍历计算面积最大值即可。
result=0
for j in range(cols):
# up[i]为j列的i处上面的第一个小于left[i][j]的行索引;down指i处下面的第一个小于left[i][j]的行索引;其中-1和rows相当于链表中的哑结点
up,down=[-1]*rows,[rows]*rows
stack=[]
for i in range(rows):
while stack and stack[-1][0]>=left[i][j]:
item=stack.pop()
down[item[1]]=i
if stack:
up[i]=stack[-1][1]
stack.append((left[i][j],i))
# print(up,down)
for i in range(rows):
result=max(result,(down[i]-up[i]-1)*left[i][j])
# print(result)
# 第四步,返回结果
return result
C++代码
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if(matrix.size()==0){
return 0;
}
int rows=matrix.size(),cols=matrix[0].size();
vector<vector<int>> left(rows,vector<int>(cols,0));
for(int i=0;i<rows;++i){
for(int j=0;j<cols;++j){
if(matrix[i][j]=='1'){
left[i][j]=(j!=0 ? left[i][j-1]+1 : 1);
}
}
}
int result=0;
for(int j=0;j<cols;++j){
vector<int> up(rows,-1);
vector<int> down(rows,rows);
stack<pair<int,int>> stk;
for(int i=0;i<rows;++i){
while(!stk.empty() && stk.top().first>=left[i][j]){
auto item=stk.top();stk.pop();
down[item.second]=i;
}
if(!stk.empty()){
up[i]=stk.top().second;
}
stk.emplace(left[i][j],i);
}
for(int i=0;i<rows;++i){
result=max(result,(down[i]-up[i]-1)*left[i][j]);
}
}
return result;
}
};