C++ using Stack 28ms (42.03%)


  • 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+1,0);//last one is the dummy varible(0), it will be used for the stack in maxArea function
        
        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);
            res = max(res, area);
        }
        return res;
    };
    
    int maxArea(vector<int>& heights){
        if(heights.size() <= 1) return 0;
        int area = 0;
        stack<int> s;
        int i = 0;
        while(i < heights.size()){
            if(s.empty() || heights[s.top()] <= heights[i]){
                s.push(i++);
            }else{
                int j = s.top();
                s.pop();
                area = max(area, heights[j] * (s.empty() ? i : i - s.top() - 1));
            }
        }
        return area;
    }     };

Log in to reply
 

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