Leetcode 85. Maximal Rectangle

Seawolf

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if matrix == None or len(matrix) == 0 or len(matrix[0]) == 0:
            return 0
        m = len(matrix)
        n = len(matrix[0])
        height = [0] * n
        res = 0
        for row in matrix:
            for i in range(n):
                height[i] = height[i] + 1 if row[i] == '1' else 0
            stack = []
            for i in range(n + 1):
                if i == n:
                    curt = -1
                else:
                    curt = height[i]
                while stack and curt <= height[stack[-1]]:
                    h = height[stack.pop()]
                    if len(stack) == 0:
                        w = i
                    else:
                        w = i - stack[-1] - 1
                    res = max(res, h * w)
                stack.append(i)
        return res