# 85. Maximal Rectangle

## 刷题内容

• https://leetcode.com/problems/maximal-rectangle/

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example:

Input:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Output: 6


Ë¼Â·1 **- Ê±¼ä¸´ÔÓ¶È: O(n^3)*- ¿Õ¼ä¸´ÔÓ¶È: O(1)***

class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int len1 = matrix.size();
if(!len1)
return 0;
int len2 = matrix[0].size();
int ans = 0;
for(int t = 0;t < len1;++t)
for(int i = 0;i < len2;++i)
{
int count1 = 0;
while(i + count1 < len2 && matrix[t][i + count1] - '0')
++count1;
if(count1)
{
int row = 1;
ans = max(ans,row * count1);
for(int j = t + 1;j < len1;++j)
{
int count2 = 0;
while(count2  <= count1 && matrix[j][i + count2] - '0')
++count2;
if(!count2)
break;
if(count1 > count2)
count1 = count2;
++row;
ans = max(ans,row * count1);
}
}
}
return ans;
}
};


Ë¼Â·2 **- Ê±¼ä¸´ÔÓ¶È: O(n^2)*- ¿Õ¼ä¸´ÔÓ¶È: O(n)***

¶ÔÉÏÊöËã·¨½øÐÐÓÅ»¯£¬¼ÆËãÃ¿¸öÊýµÄ¸ß¶ÈºÍÕâ¸ö¸ß¶ÈÏò×óµÄÎ»ÖÃºÍÏòÓÒµÄÎ»ÖÃ£¬ÕâÑùÖ»ÒªÔÚO(n^2)µÄÊ±¼ä¸´ÔÓÄÚ¾ÍÄÜÍê³É

class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int len1 = matrix.size();
if(!len1)
return 0;
int len2 = matrix[0].size();
int height[len2],l[len2],r[len2];
memset(height,0,sizeof(height));
memset(l,0,sizeof(l));
for(int i = 0;i < len2;++i)
r[i]  = len2;
int ans = 0;
for(int i = 0;i < len1;++i)
{
int t_l = 0,t_r = len2;
for(int j = 0;j < len2;++j)
if(matrix[i][j]-'0')
height[j] = height[j] + 1;
else
height[j] = 0;
for(int j = 0;j < len2;++j)
if(matrix[i][j]-'0')
l[j] = max(l[j],t_l);
else
{
t_l = j + 1;
l[j] = 0;
}
for(int j = len2 - 1;j >= 0;--j)
if(matrix[i][j]-'0')
r[j] = min(r[j],t_r);
else
{
t_r = j;
r[j] = len2;
}
for(int j = 0;j < len2;++j)
ans = max(ans,(r[j] - l[j]) * height[j]);
}
return ans;
}
};