nikunjsoni

85

Apr 5th, 2021
73
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int maximalRectangle(vector<vector<char>>& matrix) {
  4.         int cLen, rLen, ans, i, j, p;
  5.         rLen = matrix.size();
  6.         if(!rLen) return 0;
  7.         cLen = matrix[0].size();
  8.         ans = 0;
  9.        
  10.         int leftMin[cLen], rightMin[cLen], height[cLen];
  11.         memset(height, 0, sizeof(height));
  12.         for(i=0; i<rLen; i++){
  13.             for(j=0; j<cLen; j++){
  14.                 if(matrix[i][j] == '1') height[j]++;
  15.                 else height[j] = 0;
  16.                 leftMin[j] = rightMin[j] = 0;
  17.             }
  18.            
  19.             leftMin[0] = -1;
  20.             for(j=1; j<cLen; j++){
  21.                 p = j-1;
  22.                 while(p >= 0 && height[p] >= height[j])
  23.                     p = leftMin[p];
  24.                 leftMin[j] = p;
  25.             }
  26.            
  27.             rightMin[cLen-1] = cLen;
  28.             for(j=cLen-2; j>=0; j--){
  29.                 p = j+1;
  30.                 while(p < cLen && height[p] >= height[j])
  31.                     p = rightMin[p];
  32.                 rightMin[j] = p;
  33.             }
  34.            
  35.             for(j=0; j<cLen; j++)
  36.                 ans = max(ans, height[j]*(rightMin[j]-leftMin[j]-1));
  37.         }
  38.         return ans;
  39.     }
  40. };
RAW Paste Data