0085：最大矩形（★★）

2015-03-26 约 279 字预计阅读 1 分钟次阅读

力扣第 85 题

题目

给定一个仅包含 0 和 1 、大小为 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

目录

0085：最大矩形（★★）

题目

分析

解答