85. Maximal Rectangle

Given a rows x cols binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

Example 1:

Input: matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]] Output: 6 Explanation: The maximal rectangle is shown in the above picture.

  • code
class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0
        
        def calRecHistogram(height):
            stack = [-1]
            maxArea = 0
            for i in range(len(height)):
                while stack[-1] != -1 and height[i] <= height[stack[-1]]:
                    curHeight = height[stack.pop()]
                    curWidth = i - 1 - stack[-1]
                    maxArea = max(maxArea, curHeight * curWidth)
                stack.append(i)
                
            while stack[-1] != -1:
                curHeight = height[stack.pop()]
                curWidth = len(height) - 1 - stack[-1]
                maxArea = max(maxArea, curHeight * curWidth)
            return maxArea
            
        
        res = 0
        height = [0] * len(matrix[0])
        for row in range(len(matrix)):
            for col in range(len(matrix[0])):
                if matrix[row][col] == "0": 
                    height[col] = 0
                else:
                    height[col] += 1
            res = max(res, calRecHistogram(height))
        
        return res