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