目录

0085:最大矩形(★★)

力扣第 85 题

题目

给定一个仅包含 01 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。

示例 1:

输入:matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出:6
解释:最大矩形如上图所示。

示例 2:

输入:matrix = [["0"]]
输出:0

示例 3:

输入:matrix = [["1"]]
输出:1

提示:

  • rows == matrix.length
  • cols == matrix[0].length
  • 1 <= row, cols <= 200
  • matrix[i][j]'0''1'

相似问题:

分析

  • 固定矩形的底在第 i 行,求出每列的高度 H[i][j],即转为问题 0084
  • 注意 H[i][j] 可以由 H[i-1][j] 递推得到,故总的时间复杂度 $O(M*N)$

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        def cal(H):
            res,sk = 0,[]
            for j,h in enumerate(H+[0]):
                while sk and sk[-1][1]>=h:
                    _,x = sk.pop()
                    i = sk[-1][0] if sk else -1
                    res = max(res,(j-i-1)*x)
                sk.append((j,h))
            return res
        res, H = 0, [0]*len(matrix[0])
        for row in matrix:
            H = [a+1 if b=='1' else 0 for a,b in zip(H,row)]
            res = max(res,cal(H))
        return res

71 ms