LEET-T0085: Maximal Rectangle

#include <bits/stdc++.h>
using namespace std;

const int N = 200 + 5;

vector<vector<char>> mat;

int height[N];

int maximalRectangle(vector<vector<char>> &mat){
    if(mat.size() == 0){
        return 0;
    }
    int row = mat.size();
    int col = mat[0].size();
    for(int j = 0; j <= col; ++j){
        height[j] = 0;
    }
    int mx = 0;
    for(int i = 0; i < row; ++i){
        for(int j = 0; j < col; ++j){
            if(mat[i][j] == '1'){
                ++height[j];
            } else {
                height[j] = 0;
            }
        }
        stack<int> stk;
        for(int j = 0; j <= col; ++j){
            while(!stk.empty() && height[stk.top()] >= height[j]){
                int cur = stk.top();
                stk.pop();
                int prv = stk.empty() ? -1 : stk.top();
                mx = max(mx, (j - prv - 1) * height[cur]);
            }
            stk.push(j);
        }
    }
    return mx;
}

int main(){

    int row, col;
    scanf("%d%d", &row, &col);
    mat.assign(row, vector<char>(col, '\0'));
    for(int i = 0; i < row; ++i){
        for(int j = 0; j < col; ++j){
            scanf(" %c", &mat[i][j]);
        }
    }
    cout << maximalRectangle(mat);

    return 0;
}