85. Maximal Rectangle

Information

  • Diffculty: Hard

  • Created: 2020-03-10 09:29:00

  • Last Motified: 2020-03-10 09:51:40

  • Tags: Array, Hash Table, Dynamic Programming, Stack

Intuition

We could handle it by rows.

In each row, it is easily to get the maximum height of the current column by DP. Because dp[i][j] = dp[i - 1][j] + 1 if matrix[i][j] is 1, else it is 0.

With this dp array, we could use the algorithm we used in problem <85. Largest Rectangle in Histogram> to get the maximum area of the rectangle ends with each node.

Solution

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        m, n = len(matrix), len(matrix[0])
        dp = [0] * (n + 1)
        max_area = 0
        for i in range(m):
            # Use DP to get the height of each column
            for j in range(n):
                if matrix[i][j] == "1":
                    dp[j] += 1
                else:
                    dp[j] = 0

            # Use stack to get the maximum area
            stack = [[-1, -1]]
            for index, height in enumerate(dp):
                i = index
                while stack[-1][0] >= height:
                    h, i = stack.pop()
                    area = h * (index - i)
                    max_area = max(area, max_area)
                stack.append([height, i])
        return max_area