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

Popular posts from this blog

Amazing Subarrays(cpp,interviewbit)

Symmetric Tree(leetcode,cpp):

sum of left leaves in a tree(leetcode).