85. 最大矩形

Difficulty
Hard
Tags
单调栈
URL
https://leetcode-cn.com/problems/maximal-rectangle/
Star
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例 1：
notion imagenotion image
输入：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
示例 3：
输入：matrix = [["0"]]
输出：0
示例 4：
输入：matrix = [["1"]]
输出：1
示例 5：
输入：matrix = [["0","0"]]
输出：0
提示：
  • rows == matrix.length
  • cols == matrix[0].length
  • 1 <= row, cols <= 200
  • matrix[i][j] 为 '0' 或 '1'
通过次数111,309提交次数213,539

法1 单调栈

思路
参考
⛸️
84. 柱状图中最大的矩形.
对于以下矩形，可以转化为如下问题：
每一层看作是柱状图，套用84题柱状图的最大面积。
第一层柱状图的高度["1","0","1","0","0"]，最大面积为1；
第二层柱状图的高度["2","0","2","1","1"]，最大面积为3；
第三层柱状图的高度["3","1","3","2","2"]，最大面积为6；
第四层柱状图的高度["4","0","0","3","0"]，最大面积为4；
所以最大面积为 6
notion imagenotion image
题解
class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        for i in range(1, len(matrix)):
            for j in range(0, len(matrix[0])):
                if matrix[i][j] == "1":
                    matrix[i][j] = 1 + int(matrix[i-1][j])
                else:
                    matrix[i][j] = "0"
        res = 0
        for i in range(0, len(matrix)):
            res = max(res, self.helper(matrix[i]))

        return res

    def helper(self, arr):
        arr = [0] + arr + [0]
        stack = []
        res = 0
        for i in range(0, len(arr)):
            while stack and int(arr[i]) < int(arr[stack[-1]]):
                h = int(arr[stack.pop()])
                w = i - stack[-1] - 1
                res = max(res, h * w)

            stack.append(i)

        return res