85 Maximal Rectangle

class Solution {
public:
    int histoRectangle(vector<int>& heights) {
        int n = heights.size();
        if ( n == 0 ) return 0;
        if ( n == 1 ) return heights[0];
        vector<int> left(n, 0);
        stack<int> s;
        s.push(0);
        for ( int i = 1; i <= n-1; i++ ) {
            while ( ! s.empty() and heights[s.top()] >= heights[i] ) s.pop();
            if ( ! s.empty() ) left[i] = s.top() + 1;
            s.push(i);
        }
        while ( ! s.empty() ) s.pop();
        s.push(n-1);
        int maxS = heights[n-1]*(n-left[n-1]);
        for ( int i = n-2; i >= 0; i-- ) {
            while ( ! s.empty() and heights[s.top()] >= heights[i] ) s.pop();
            if ( s.empty() ) maxS = max(maxS, heights[i] * (n-left[i]));
            else maxS = max(maxS, heights[i]*(s.top() - left[i]));
            s.push(i);
        }
        return maxS;
    }
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if ( m == 0 ) return 0;
        int n = matrix[0].size();
        if ( n == 0 ) return 0;
        vector<int> histo(n, 0);
        int maxS = 0;
        for ( int i = 0; i <= m-1; i++ ) {
            for ( int j = 0; j <= n-1; j++ ) {
                if ( matrix[i][j] == '0' ) histo[j] = 0;
                else histo[j] += 1;
            }
            maxS = max(maxS, histoRectangle(histo));
        }
        return maxS;
    }
};

Notes

• Use the "Largest Rectangle in Histogram" solution!
• Things are much different for "maximal square" haha~