Easy histogram area based approach in C++


#1
int helper(vector<int>histogram)
{
    stack<int>stk;
    vector<int>left(histogram.size()),right(histogram.size());
    stk.push(0);
    left[0]=-1;
    right[right.size()-1]=right.size();
    for(int i=1;i<histogram.size();i++)
    {
        while(!stk.empty() && histogram[stk.top()]>=histogram[i])
        {
            stk.pop();
        }
        left[i]=(stk.empty()?-1:stk.top());
        stk.push(i);
    }
    while(!stk.empty())
    {
        stk.pop();
    }
    stk.push(histogram.size()-1);
    for(int i=histogram.size()-2;i>=0;i--)
    {
        while(!stk.empty() && histogram[stk.top()]>=histogram[i])
        {
            stk.pop();
        }
        right[i]=(stk.empty()?histogram.size():stk.top());
        stk.push(i);
    }
    int ans=0;
    for(int i=0;i<histogram.size();i++)
    {
        ans=max(ans,(right[i]-left[i]-1)*histogram[i]);
    }
    return ans;
}
int Solution::maximalRectangle(vector<vector<int> > &A) 
{
    vector<int>histogram(A[0].size());
    histogram=A[0];
    int ans=helper(histogram);
    for(int i=1;i<A.size();i++)
    {
        for(int j=0;j<A[i].size();j++)
        {
            histogram[j]=(A[i][j]==0?0:1+histogram[j]);
        }
        ans=max(ans,helper(histogram));
    }
    return ans;
}