leetcode [85] 最大矩形

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例:

输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6

思路来自题解:

在leetcode 84 柱状图中最大的矩形的基础上，计算得到每一层的柱状图，得到每一层的最大面积。注意如果遇到0，则该高度为0。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        if len(heights) == 0:
            return 0

        maxarea = 0
        stack = [-1]
        for i, h in enumerate(heights):
            if len(stack) == 1:
                stack.append(i)
                continue
            while h <= heights[stack[-1]] and len(stack) > 1:
                tmp = stack.pop()
                maxarea = max(maxarea, heights[tmp] * (i - 1 - stack[-1]))
            stack.append(i)

        while len(stack) > 1:
            tmp = stack.pop()
            maxarea = max(maxarea, heights[tmp] * (len(heights) - 1 - stack[-1]))
            
        return maxarea
    
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if len(matrix) == 0:
            return 0
        if len(matrix[0]) == 0:
            return 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                matrix[i][j] = int(matrix[i][j])

        maxarea = self.largestRectangleArea(matrix[0])
        for i in range(1, len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] != 0:
                    matrix[i][j] += matrix[i - 1][j]
            maxarea = max(maxarea, self.largestRectangleArea(matrix[i]))

        return maxarea