LeetCode

Appearance

85. Maximal Rectangle ​

题目 ​

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

 

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

Example 2:

Input: matrix = [["0"]]
Output: 0

Example 3:

Input: matrix = [["1"]]
Output: 1

 

Constraints:

  • rows == matrix.length
  • cols == matrix[i].length
  • 1 <= row, cols <= 200
  • matrix[i][j] is '0' or '1'.
Related Topics
  • 栈
  • 数组
  • 动态规划
  • 矩阵
  • 单调栈

  • 👍 1743
  • 👎 0

    • 思路 ​

    重新塑造整个2d数组，将2d数组每一行转换成一个单调栈，分别求每个单调栈的中最大的矩形面积

    推导过程如下

    text
    origin matrix
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]

👇

transfer to monotonic stack list for every row

[1, 0, 1, 0, 0]  ➡️ largest area: 1
[2, 0, 2, 1, 1]  ➡️ largest area: 3
[3, 1, 3, 2, 2]  ➡️ largest area: 6 ✅
[4, 0, 0, 3, 0]  ➡️ largest area: 6

    解法 ​

    py
    from typing import List
# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:

        res = 0
        rows = len(matrix)
        cols = len(matrix[0])
        heights = [0] * cols

        def findMaxArea(heights: List[int])  -> int:
            area = 0
            heights.append(0)
            stack = []
            for i in range(len(heights)):

                while stack and heights[i] < heights[stack[-1]]:
                    index = stack.pop()
                    width = i if not stack else i - (stack[-1] + 1)
                    area = max(area, heights[index] * width)
                stack.append(i)
            heights.pop()
            return area

        for i in range(rows):
            for j in range(cols):
                if matrix[i][j] == '1':
                    heights[j] += 1
                else:
                    heights[j] = 0
            res = max(findMaxArea(heights), res)

        return res

# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    • N rows, M = cols
    • 时间复杂度 O(N*M)
    • 空间复杂度 O(N*M)