85. 最大矩形

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int Y = matrix.size();
        if(Y == 0) return 0;
        int X = matrix[0].size();
        int ans = 0;
        vector<vector<int> > left(Y+2, vector<int>(X+1, 0));
        for(int yy = 1; yy <= Y; yy++) {
            for(int xx = 1; xx <= X; xx++) {
                left[yy][xx] = matrix[yy-1][xx-1] == '1' ? left[yy][xx-1] + 1 : 0;
            }
        }
        for(int xx = 1; xx <= X; xx++) {
            stack<int> S;
            S.push(0);
            for(int yy = 1; yy < left.size(); yy++) {
                while(S.top() != 0 && left[yy][xx] <= left[S.top()][xx]) {
                    int height = left[S.top()][xx];
                    S.pop();
                    ans = max(ans, height * (yy - S.top() - 1));
                }
                S.push(yy);
            }
        }
        return ans;
    }
};

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int Y = matrix.size();
        if(Y == 0) return 0;
        int X = matrix[0].size();
        int ans = 0;
        vector<vector<int> > left(Y+1, vector<int>(X+1, 0));
        for(int yy = 1; yy <= Y; yy++) {
            for(int xx = 1; xx <= X; xx++) {
                left[yy][xx] = matrix[yy-1][xx-1] == '1' ? left[yy][xx-1] + 1 : 0;
            }
        }
        for(int yy = 1; yy <= Y; yy++) {
            for(int xx = 1; xx <= X; xx++) {
                if(left[yy][xx] == 0) continue;
                int kk = yy - 1, jj = yy + 1;
                while(kk && left[kk][xx] >= left[yy][xx]) kk--;
                while(jj <= Y && left[jj][xx] >= left[yy][xx]) jj++;
                ans = max(ans, left[yy][xx] * (jj - kk - 1));
            }
        }
        return ans;
    }
};