首页 > 代码库 > 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