85. Maximal Rectangle

Hard

---

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.

Example 2:

Input: matrix = [["0"]]
Output: 0

Example 3:

Input: matrix = [["1"]]
Output: 1

Constraints:

• rows == matrix.length

• cols == matrix[i].length

• 1 <= row, cols <= 200

• matrix[i][j] is '0' or '1'.

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        for i in range(len(matrix[0])):
            matrix[0][i] = int(matrix[0][i])
        for i in range(1, len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == "0":
                    matrix[i][j] = 0
                elif matrix[i][j] != "0":
                    matrix[i][j] = int(matrix[i][j]) + int(matrix[i-1][j])
        result = 0
        for index in range(len(matrix)):
            # print(matrix[index])
            result = max(result, self.max_histogram_rectangle(matrix[index]))
        return result
    
    def max_histogram_rectangle(self, height):
        height.append(0)
        stack = [-1]
        result = 0
        for index in range(len(height)):
            while height[index] < height[stack[-1]]:
                h = height[stack.pop()]
                w = index-1 - stack[-1]
                result = max(result, h*w)
            stack.append(index)
        return result