Advertisement
mickypinata

LEET-T0085: Maximal Rectangle

Nov 17th, 2021
812
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 200 + 5;
  5.  
  6. vector<vector<char>> mat;
  7.  
  8. int height[N];
  9.  
  10. int maximalRectangle(vector<vector<char>> &mat){
  11.     if(mat.size() == 0){
  12.         return 0;
  13.     }
  14.     int row = mat.size();
  15.     int col = mat[0].size();
  16.     for(int j = 0; j <= col; ++j){
  17.         height[j] = 0;
  18.     }
  19.     int mx = 0;
  20.     for(int i = 0; i < row; ++i){
  21.         for(int j = 0; j < col; ++j){
  22.             if(mat[i][j] == '1'){
  23.                 ++height[j];
  24.             } else {
  25.                 height[j] = 0;
  26.             }
  27.         }
  28.         stack<int> stk;
  29.         for(int j = 0; j <= col; ++j){
  30.             while(!stk.empty() && height[stk.top()] >= height[j]){
  31.                 int cur = stk.top();
  32.                 stk.pop();
  33.                 int prv = stk.empty() ? -1 : stk.top();
  34.                 mx = max(mx, (j - prv - 1) * height[cur]);
  35.             }
  36.             stk.push(j);
  37.         }
  38.     }
  39.     return mx;
  40. }
  41.  
  42. int main(){
  43.  
  44.     int row, col;
  45.     scanf("%d%d", &row, &col);
  46.     mat.assign(row, vector<char>(col, '\0'));
  47.     for(int i = 0; i < row; ++i){
  48.         for(int j = 0; j < col; ++j){
  49.             scanf(" %c", &mat[i][j]);
  50.         }
  51.     }
  52.     cout << maximalRectangle(mat);
  53.  
  54.     return 0;
  55. }
  56.  
Advertisement
RAW Paste Data Copied
Advertisement