↓Skip to main content
  1. Posts/

LeetCode-85 最大矩形

·1 min·
Table of Contents

LeetCode-85 最大矩形 #

Solution 1 #

枚举行, 每一行的问题是求柱状图中的最大矩形面积, 使用单调栈计算.

代码如下:

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return 0

        def maxRec(heights):
            n = len(heights)

            s = []
            left = [-1] * n
            for i in range(n):
                while s and heights[s[-1]] >= heights[i]:
                    s.pop()
                if s:
                    left[i] = s[-1]
                s.append(i)

            s = []
            right = [n] * n
            res = 0
            for i in range(n - 1, -1, -1):
                while s and heights[s[-1]] >= heights[i]:
                    s.pop()
                if s:
                    right[i] = s[-1]
                res = max(res, heights[i] * (right[i] - left[i] - 1))
                s.append(i)
            return res
        
        m, n = len(matrix), len(matrix[0])
        heights = [0 for _ in range(n)]
        ans = 0
        for i in range(m):
            for j in range(n):
                heights[j] = (heights[j] if i > 0 else 0) + 1 if matrix[i][j] == '1' else 0
            ans = max(ans, maxRec(heights))
        return ans