剑指 Offer II 040. 矩阵中最大的矩形

剑指 Offer II 040. 矩阵中最大的矩形

class Solution:
    def largestRectangleArea(heights: List[int]) -> int:
        heights.append(0)   #最后一个柱形高度为0，列表剩下的元素全都会pop出计算其为高度时的最大矩形面积
        lenh=len(heights)
        maxArea=0
        h=[-1]
        for i in range (lenh):
            while h[-1]!=-1 and heights[i]<heights[h[-1]]:
                area_height=heights[h[-1]]
                h.pop()
                area_width=i-h[-1]-1     #只剩一个柱形元素时，左边界index可当作-1
                maxArea=max(maxArea,area_height*area_width)
            h.append(i)        #此时heights[i]>heights[h[-1]]
        return maxArea
    def maximalRectangle(self, matrix: List[str]) -> int:
        if not matrix:
            return 0
        row,col=len(matrix),len(matrix[0])
        height,ans=[0]*col,0
        for i in range(row):
            for j in range (col):
                if matrix[i][j]=='0': 
                    height[j]=0
                elif i>0 and matrix[i-1][j]=='0':   #其余行 and matrix[i][j]=1 and matrix[i-1][j]=0
                    height[j]=int(matrix[i][j])
                else:            #第一行 且 matrix[i][j]=1 Or 其余行 且 matrix[i][j]=1 且 matrix[i-1][j]=1
                    height[j]+=1
            ans=max(ans,Solution.largestRectangleArea(height))   
        return ans