85.Maximal Rectangle

Tags: [dp], [area], [trick]

Com: {fb}

Link: https://leetcode.com/problems/maximal-rectangle/#/description

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

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 6.

Solution: DP

class Solution(object):
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix or not matrix[0]:
            return 0

        num_of_rows = len(matrix)
        num_of_cols = len(matrix[0])

        dp = [[0 for _ in xrange(num_of_cols)] for _ in xrange(num_of_rows)]
        for row in xrange(num_of_rows):
            dp[row][0] = int(matrix[row][0])

        for row in xrange(num_of_rows):
            for col in xrange(1, num_of_cols):
                if matrix[row][col] == '0':
                    continue

                dp[row][col] = 1 + dp[row][col - 1]

        max_area = 0
        for row in xrange(num_of_rows):
            for col in xrange(num_of_cols):
                if dp[row][col] == 0:
                    continue

                height = 1

                # look up
                tmp_row = row
                while tmp_row - 1 >= 0 and dp[tmp_row - 1][col] >= dp[row][col]:
                    tmp_row -= 1

                if tmp_row < row:
                    height += row - tmp_row

                # look down
                tmp_row = row
                while tmp_row + 1 < num_of_rows and dp[tmp_row + 1][col] >= dp[row][col]:
                    tmp_row += 1

                if tmp_row > row:
                    height += tmp_row - row

                area = height * dp[row][col]
                max_area = max(max_area, area)

        return max_area

Revelation:

• dp[row][col] stores the the max length of continuous edge which is end by [row][col].
• while tmp_row - 1 >= 0 and dp[tmp_row - 1][col] >= dp[row][col]: means try tmp_row - 1, if it's OK, then we do tmp_row -= 1, if it's not OK, we stop, the tmp_row at that moment is what we want.

Note:

• Time complexity = O(m * n * m), m is the number of rows, n is the number of cols.