85.-maximal-rectangle.md

85. Maximal Rectangle

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix: return 0
        n = len(matrix)
        m = len(matrix[0])

        dp = [[0] * (m + 1) for _ in range(n)]
        for j in range(m):
            dp[0][j] = 1 if matrix[0][j] == "1" else 0

        for i in range(1, n):
            for j in range(m):
                dp[i][j] = dp[i - 1][j]  + 1 if matrix[i][j] == "1" else 0
        # print(dp)
        ans = 0 
        for i in range(n):
            max_ = self.getRec(i , m, dp)
            ans = max(max_,ans)
        return ans


    def getRec(self, i , m , dp):

        max_ = 0
        stack = [-1]

        for j in range(m + 1):
            while dp[i][j] < dp[i][stack[-1]]:
                cur = dp[i][stack.pop()]
                max_ = max(max_, cur * (j - stack[-1] - 1))
            stack.append(j)
        return max_