C++ Divide & Conquer 32ms


  • 0
    class Solution {
    public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.empty()) return 0;
        int m = matrix.size();
        int n = matrix[0].size();
        int res = 0;
        vector<int> height(n,0);
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int val = matrix[i][j] - '0';
                if(val == 0){height[j] = 0;}
                else{height[j] = height[j] + val;}
            }
            int area = maxArea(height, 0, n-1);
            res = max(res, area);
        }
        return res;
    }
    
    int maxArea(vector<int>& height, int s, int e){
        if(s == e) return height[s];
        int m = s + (e - s)/2;
        int max_area = maxArea(height, s, m);
        max_area = max(maxArea(height, m+1, e), max_area);
        max_area = max(maxCombinArea(height, s, m, e), max_area);
        return max_area;
    }
    
    int maxCombinArea(vector<int>& height, int s, int m, int e){
        int i = m, j = m+1;
        int max_area = 0, h = min(height[i], height[j]);
        while( i >= s && j <= e){
            h = min(h, min(height[i],height[j]));
            max_area = max(max_area, h*(j - i + 1));
            if(i == s){++j;}
            else if (j == e){--i;}
            else{
                if(height[i-1] > height[j+1]){--i;}
                else{++j;}
            }
        }
        return max_area;
    }     };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.