Easy stack based approach


#1
int helper(vector<int>& heights) 
{
    if(heights.size()==0)
    {
        return 0;
    }
    else if(heights.size()==1)
    {
        return heights[0];
    }
    else
    {
    int rb[heights.size()],lb[heights.size()],i,j;
    stack<int>stk;
    rb[heights.size()-1]=heights.size();
    stk.push(heights.size()-1);
    for(i=heights.size()-2;i>=0;i--)
    {
        while(!stk.empty() && heights[i]<=heights[stk.top()])
        {
            stk.pop();
        }
        if(stk.empty())
        {
            rb[i]=heights.size();
        }
        else
        {
            rb[i]=stk.top();
        }
        stk.push(i);
    }
    while(!stk.empty())
    {
        stk.pop();
    }
    stk.push(0);
    lb[0]=-1;
    for(i=1;i<heights.size();i++)
    {
        while(!stk.empty() && heights[i]<=heights[stk.top()])
        {
            stk.pop();
        }
        if(stk.empty())
        {
            lb[i]=-1;
        }
        else
        {
            lb[i]=stk.top();
        }
        stk.push(i);
    }
    int ans=0;
    for(i=0;i<heights.size();i++)
    {
        int area=heights[i]*(rb[i]-lb[i]-1);
        ans=max(ans,area);
    }
    return ans;
    }
}

int Solution::maximalRectangle(vector<vector > &matrix)
{
if(matrix.size()==0)
{
return 0;
}
int i,j,m=matrix.size(),n=matrix[0].size(),res=0;
vectordp(n,0);
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(matrix[i][j]!=0)
{
dp[j]+=(matrix[i][j]);
}
else
{
dp[j]=0;
}
}
res=max(res,helper(dp));
}
return res;
}