首页 > 代码库 > LeetCode: Maximal Rectangle [085]
LeetCode: Maximal Rectangle [085]
【题目】
【题意】
给定一个由0和1填充的二维矩阵，找一个全是1的最大矩形【思路】
扫描二维矩阵，凡是扫到值为1的块时候，以当前块为矩形的左上角区块拓展，找最大矩阵。先找出以每个“1”区块为左上角区块的最大矩形，然后求出最大全局的最大矩形。
以下图为例，我们就看matrix[0][0]，它的值正好是1 ，则以他为左上角的矩形共有3个，如左图所示。其中最大的矩形面积为8，如右图所示的绿色矩形
【代码】
class Solution {
public:
int maximalRectangle(vector<vector<char> > &matrix) {
int rows = matrix.size();
if(rows==0)return 0;
int cols = matrix[0].size();
if(cols==0)return 0;
int maxArea=0;
for(int i=0; i<rows; i++){
for(int j=0; j<cols; j++){
if(matrix[i][j]=='1'){
//求以该位置为左上角的最大矩形
int minHeight=INT_MAX;
int width=0;
int ti=i;
while(ti<rows && matrix[ti][j]=='1'){
width++;
int height=0; //求横向高度
while(j+height<cols && matrix[ti][j+height]=='1')height++;
//更新最小高度
if(height<minHeight)minHeight=height;
//计算当前面积
int curArea = width*minHeight;
//更新最大面积
if(curArea>maxArea)maxArea=curArea;
ti++;
}
}
}
}
return maxArea;
}
};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。