Advertisement
YEZAELP

LeetCode: Maximal Rectangle

Nov 4th, 2021
1,041
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.40 KB | None | 0 0
  1. class Solution {
  2. public:
  3.    
  4.     using pi = pair <int, int>;
  5.     int ar[210][210];
  6.     int up[210][210];
  7.    
  8.     int maximalRectangle(vector<vector<char>>& matrix) {
  9.         int ans = 0;
  10.         int n = matrix.size();
  11.         if(n == 0) return ans;
  12.         int m = matrix[0].size();
  13.         if(m == 0) return ans;
  14.         for(int i=1;i<=n;i++){
  15.             for(int j=1;j<=m;j++){
  16.                 if(matrix[i-1][j-1] == '1'){
  17.                     ar[i][j] = 1;
  18.                     up[i][j] = up[i-1][j] + 1;
  19.                 }
  20.                 else ar[i][j] = 0;
  21.             }
  22.         }
  23.         for(int i=1;i<=n;i++){
  24.             stack <int> st;
  25.             for(int j=1;j<=m;j++){
  26.                 while(!st.empty() and up[i][st.top()] > up[i][j]){
  27.                     int area = 0;
  28.                     int prej = st.top(); st.pop();
  29.                     if(st.empty()) area = up[i][prej] * (j - 1);
  30.                     else area = up[i][prej] * (j - st.top() - 1);
  31.                     ans = max(ans, area);
  32.                 }
  33.                 st.push(j);
  34.             }
  35.             while(!st.empty()){
  36.                 int area = 0;
  37.                 int prej = st.top(); st.pop();
  38.                 if(st.empty()) area = up[i][prej] * m;
  39.                 else area = up[i][prej] * (m - st.top());
  40.                 ans = max(ans, area);
  41.             }
  42.         }
  43.        
  44.         return ans;
  45.     }
  46. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement