Maximal Rectangle

题目描述

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

解题方法

brute force

取任意两点为两个对角点，然后check是否包含为0的元素。

O(n^6)

左上角

只取一个左上角，然后逐行找行能达到的最右边，计算面积

利用 largest rectangle in histogram

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

如果是一个这样的matrix, 逐行扫描的话，其实就是bar的高度

• 第一行 [0, 1, 0, 1, 0]
• 第二行 [1, 2, 0, 2, 1]
• 第三行 [2, 3, 0, 3, 2] ...

那么其实就是和largest rectangle in histogram一样的题目了

时间复杂度O(n ^ 2), 空间复杂度为O(n)

Solution

class Solution(object):
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix:
            return 0
        rowNum = len(matrix)
        colNum = len(matrix[0])
        result = 0

        height = [0 for j in range(colNum)]
        for i in range(rowNum):
            for j in range(colNum):
                if matrix[i][j] == "0":
                    height[j] = 0
                else:
                    height[j] += 1
            curMax = self.largestRectangleArea(height)
            result = curMax if curMax > result else result

        return result

Reference