codebuddy week10

MaxRectangleInBinaryMatrix.py

class Solution:
    # @param A : list of list of integers
    # @return an integer
        
    def histarea(self,h):
        s = list() 
        maxarea = 0 
        i= 0
        area = 0
        while i < len(h): 
            if (not s) or (h[s[-1]] <= h[i]): 
                s.append(i) 
                i += 1
            else: 
                top = s.pop() 
                area = (h[top] * ((i - s[-1] - 1) if s else i)) 
            maxarea = max(maxarea, area) 
        while s: 
            top = s.pop() 
            area = (h[top] * ((i - s[-1] - 1) if s else i)) 
            maxarea = max(maxarea, area) 
        return maxarea 
    
    
    
    def maximalRectangle(self, A):
        l = A[0]
        area = self.histarea(l)
        maxarea = area
        for i in range(1,len(A)):
            for j in range(len(A[i])):
                if A[i][j] == 1:
                    l[j] = l[j] + 1
                else:
                    l[j] = 0
            area = self.histarea(l)
            if area > maxarea:
                maxarea = area

        return maxarea