Leetcode 85. Maximal Rectangle

Maximal Rectangle :

給定一個由 0 和 1 組成的矩陣，求其中最大的矩形面積，其中矩形中的元素都是 1。

Python

對於每一列，我們可以維護一個單調棧，棧中保存的是當前列的矩形的高度。我們可以使用這個棧來計算當前列的最大矩形面積。對於每一列，我們從棧頂開始往下遍歷，如果當前的高度比棧頂的高度大，則將當前的高度入棧。如果當前的高度比棧頂的高度小，則將棧頂的高度出棧，併計算出棧高度所對應的矩形面積。我們重複這個過程，直到遇到一個比當前高度小的元素，或者棧為空。最後，我們將所有元素出棧，併計算出棧元素所對應的矩形面積，就可以得到最大的矩形面積了。

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

Python

相關