AC Python code by solving 'largest rectangle in histogram' row by row


  • 0
    H
    class Solution(object):
        def maximalRectangle(self, matrix):
            """
            :type matrix: List[List[str]]
            :rtype: int
            """
            m = len(matrix)
            if m == 0:  return 0
            n = len(matrix[0])
            height = [0]*(n+2) # height[0] and height[n+1] are dummies
            max_area = 0
            # search row by row 
            for row in matrix:
                # treat the row as ground and calculate height for each position
                for j in range(n):
                    if row[j] == '1': height[j+1] += 1
                    else:   height[j+1] = 0
                # solve the 'largest rectangle in histogram'
                stack = [0]
                for j in range(1, n+2):
                    while height[j] < height[stack[-1]]:
                        h = height[stack[-1]]
                        stack.pop()
                        w = j - stack[-1] - 1
                        max_area = max(h*w, max_area)
                    stack.append(j)
            
            return max_area
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.