Easy C++ quadratic solution using Maximum Histogram Area concept


#1
int maximumAreaHistogram(vector<int> heights){
        vector<int> nsr, nsl;
        stack<int> st1, st2;
        for(int i=0; i<heights.size(); i++){
            while(!st1.empty() && heights[st1.top()]>=heights[i]) st1.pop();
            if(st1.empty()) nsl.push_back(-1);
            else{
                nsl.push_back(st1.top());
            }
            st1.push(i);
        }
        for(int i=heights.size()-1; i>=0; i--){
            while(!st2.empty() && heights[st2.top()]>=heights[i]) st2.pop();
            if(st2.empty()) nsr.push_back(heights.size());
            else{
                nsr.push_back(st2.top());
            }
            st2.push(i);
        }
        reverse(nsr.begin(), nsr.end());
        vector<int> width;
        for(int i=0; i<nsl.size(); i++){
            width.push_back((nsr[i]-nsl[i]-1)*heights[i]);
        }
        return *max_element(width.begin(), width.end());
    }

int Solution::maximalRectangle(vector<vector<int> > &matrix) {
     if(matrix.empty()) return 0;
        int n= matrix.size(), m= matrix[0].size();
        vector<int> v;
        for(int j=0; j<m; j++){
            v.push_back(matrix[0][j]);
        }
        int mx =maximumAreaHistogram(v);
        for(int i=1; i<n; i++){
            for(int j=0; j<m; j++){
                if(matrix[i][j]==0) v[j]=0;
                else v[j]+=(matrix[i][j]);
            }
            mx= max(maximumAreaHistogram(v), mx);
        }
        return mx;
}