首页 > 代码库 > Maximal Rectangle
Maximal Rectangle
Given a 2D binary matrix filled with 0‘s and 1‘s, find the largest rectangle containing all ones and return its area.
题意:在一个只有0、1的矩阵中找到一个面积最大的矩形,它内部所有的元素都是1。
算法:一开始,理解错了题意,后来在网上看了一下,终于弄明白了,用到了动态规划的思想,首先遍历矩阵,用一个二维数组A[i][j]表示第i行,以第j个元素为结尾的连续1的个数,遍历一次矩阵就可以得到,然后计算一matrix[i][j]为右下角的全1矩阵的最大值,也是遍历,不过遍历的是A数组,找到以第i行第j列为右下角的最大全1矩阵的面积,只要i向上遍历就可以了,找最小宽,然后算面积,如果面积比当前保存的面积大,就更新面积。写得不太清楚,有点乱,不过理解了就简单了。代码如下:
1 class Solution { 2 public: 3 int maximalRectangle(vector<vector<char> > &matrix) { 4 if(matrix.size()==0||matrix[0].size()==0) return 0; 5 int m[matrix.size()+1][matrix[0].size()+1]; 6 int len1=matrix.size(); 7 int len2=matrix[0].size(); 8 for(int i=0;i<=len1;i++) m[i][0]=0; 9 for(int i=1;i<=len1;i++)10 {11 for(int j=1;j<=len2;j++)12 {13 if(matrix[i-1][j-1]==‘1‘)14 {15 m[i][j]=m[i][j-1]+1;16 }17 else m[i][j]=0;18 }19 }20 21 int ret=0;22 23 for(int i=1;i<=matrix.size();i++)24 {25 for(int j=1;j<=matrix[0].size();j++)26 {27 int width=m[i][j];28 int k=i;29 while(k>0)30 {31 if(m[k][j]==0) break;32 width=min(width,m[k][j]);33 ret=max(ret,width*(i-k+1));34 k--;35 }36 }37 }38 return ret;39 }40 };
Maximal Rectangle
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。