85. Maximal Rectangle

https://leetcode.com/problems/maximal-rectangle/

Same approach as 84

Need to build a histogram based on the matrix

class Solution:
    def largestRectangle(self,nums):
        n = len(nums)
        left = [0] *n
        right = [0] * n
        for i in range(n):
            left[i] = i
            while left[i]- 1 >= 0 and nums[left[i]-1] >= nums[i]:
                left[i] = left[left[i]-1]
        
        for i in range(n-1,-1,-1):
            right[i] = i
            while right[i]+1 < n and nums[i] <= nums[right[i]+1]:
                right[i] = right[right[i]+1]
        
        res = 0
        for i in range(n):
            res = max(res,nums[i] * (right[i]-left[i]+1))
        return res
            
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        #build the nums row by row
        mat = [[int(i) for i in row] for row in matrix]
        
        for i in range(1,len(mat)):
            for j in range(len(mat[0])):
                if mat[i][j] == 1:
                    mat[i][j] += mat[i-1][j]
        
        res = 0
        for row in mat:
            res = max(res,self.largestRectangle(row))
        return res