85. Maximal Rectangle
难度:Hard
刷题内容
原题连接
- 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)***
µÚÒ»ÖÖ±©Á¦µÄ·½·¨È¥½â£¬ÏÈÇó³öÿһ¸öÊýÏòÓÒÓжàÉÙ¸ö¡°1¡±£¬¼Ç¼Ï³¤¶Ècount1£¬ÔÚÕâ¸öÊýµÄλÖÃÏòÏÂÑ°ÕÒ£¬ÈôÏÂÃæµÄ³¤¶ÈСÓÚcount1£¬Ôòcount1È¡½ÏСµÄÖµ¡£ÈôΪ0¾Í¼ÆËã¾ØÕóµÄ´óС£¬Ö±µ½±éÀúËùÓеÄÊý¡£
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;
}
};
