Maximal Rectangle in given matrix with 1,0(cpp, leetcode)
Maximal Rectangle in given matrix with 1,0(cpp, leetcode)
==============================================
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
========================================================================================
code ....
class Solution {
public:
int largestRectangleArea(vector<int>& a)
{
if(a.size()==0)
return 0;
else if(a.size()==1)
return a[0];
stack <int>s;
int i=0;
int maxm=0;
int area=0;
while(i<a.size())
{
if(s.empty() || a[i]>=a[s.top()])
{
s.push(i);
i++;
}
else
{
int top=s.top();
s.pop();
if(s.empty())
{
area=i*a[top];
}
else
{
area=a[top]*(i-s.top()-1);
}
maxm=max(maxm,area);
}
}
while(!s.empty())
{
int top=s.top();
s.pop();
if(s.empty())
{
area=i*a[top];
}
else
{
area=a[top]*(i-s.top()-1);
}
maxm=max(maxm,area);
}
return maxm;
}
int maximalRectangle(vector<vector<char>>& matrix)
{
if(matrix.size()==0)
return 0;
vector<int>t;
t.resize(matrix[0].size(),0);
// memset(t,0,sizeof(t));
int maxm=0;
for(int i=0;i<matrix.size();i++)
{
for(int j=0;j<matrix[0].size();j++)
{
if(matrix[i][j]=='0')
t[j]=0;
else
t[j]++;
}
int x=largestRectangleArea(t);
maxm=max(maxm,x);
}
return maxm;
}
};
Comments
Post a Comment