[LeetCode] Maximal Rectangle

At first, I thought this one will be similar to Maximal Square in 2D Array.
But soon I realize this one is harder than finding squares.
The solution is not based on finding squares at all – instead, it’s separating the 2D array into multiple histograms.
If we cover the lower half of the matrix, we can easily see that the answer becomes
finding the maximal rectangle in histograms.

The way to do that is already described in my other article
Therefore we just need to separate them into histograms.

class Solution:
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        def largestRectangleArea(heights):
            loc = []
            stack = []
            ans = 0
            for i, e in enumerate(heights):
                if i == 0 or e >= stack[-1]:
                    loc.append(i)
                    stack.append(e)
                else:
                    # pop and calculate
                    while len(stack) > 0 and e < stack[-1]:
                        h = stack.pop()
                        start = loc.pop()
                        size = h * (i - start)

                        if size > ans: ans = size
                    loc.append(start)
                    stack.append(e)

            while len(stack) > 0:
                h = stack.pop()
                start = loc.pop()
                size = h * (len(heights) - start)
                if size > ans: ans = size
            return ans

        m = len(matrix)
        n = len(matrix[0])

        hist = [[0 for j in range(n)] for i in range(m)]

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == '1':
                    if i == 0:
                        hist[i][j] = 1
                    else:
                        hist[i][j] = hist[i-1][j] + 1
        res = 0
        for i in range(m):
            histogram = hist[i]
            res = max(res, largestRectangleArea(histogram))

        return res