LeetCode 刷题记录: 85. Maximal Rectangle [Python]

原题

https://leetcode.com/problems/maximal-rectangle/

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

思路

大致思路和 84. Largest Rectangle in Histogram 相同，对于每个row判断如果为1则高度叠加，否则高度清零。

代码

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        height=[0] *(len(matrix[0])+1)
        ans=0
        for row in matrix:
            for i in range(len(matrix[0])):
                height[i]=height[i]+1 if row[i]=='1' else 0
            stack=[-1]
            for i in range(len(matrix[0])+1):
                while height[i]<height[stack[-1]]:
                    h=height[stack.pop()]
                    w=i-stack[-1]-1
                    ans=max(ans,h*w)
                stack.append(i)
        return ans

# LeetCode

支付宝

微信

Paypal Buy me a coffee

LeetCode 刷题记录: 85. Maximal Rectangle [Python]

原题

思路

代码

喜欢这篇文章？打赏一下作者吧

评论

分类

标签

最新文章

归档

最新文章

归档

Your browser is out-of-date!