Участник:Novitskiy97/Maximal Rectangle

Материал из DISCOPAL
Перейти к: навигация, поиск

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

Python 3

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if len(matrix) < 1: 
            return 0
        hist = [self.prefixSum(m) for m in matrix]
        rows, cols = len(hist), len(hist[0])
        maxarea = 0
        for i in range(cols):
            h = [row[i] for row in hist]
            area = self.maxHistRec(h)
            maxarea = max(maxarea, area)
        return maxarea
 
    def prefixSum(self,row):
        dp = [0] * len(row)
        for i, v in enumerate(row):
            dp[i] = dp[i - 1] + 1 if int(v) == 1 else 0
        return dp       
 
    def maxHistRec(self,hist):
        h = [-1] + hist + [-1]
        stack = [0]
        area = 0
        for i in range(len(h)):
            while h[stack[-1]] > h[i]:
                j = stack.pop()
                area = max(area, h[j] * (i - stack[-1] - 1))
            stack.append(i)
        return area