首页 > 代码库 > Maximal Rectangle

Maximal Rectangle

2024-07-28 08:46:01   224人阅读

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


联系
我们