Python stack solution with detailed comments


  • 0
    I
    class Solution(object):
        def largestRectangleArea(self, heights):
            """
            :type heights: List[int]
            :rtype: int
            """
            # idea is that we iterate thru all heights, and add them to a stack
            # stack invariant is that top items are higher than bottom items.
            # if a new height H is being added to the stack that violates the invariant, we keep popping
            # from the stack (call popped height H') until H > H'. We then know that a rectangle of height H' started from
            # the x coordinate of H` and ended at the x coordinate of H.
            
            # Example we have heights = [2,1,2]
            # 1. add 2 to stack. stack: [(x=0,h=2)]
            # 2. trying to add 1 to stack, pop off 2. Rectangle of height 2 started at x=0 and ended at x=1, max_area = 2
            #    stack: [(x=0,h=1)]
            # 3. add 2 to stack. stack: [(x=0,h=1),(x=2,h=2)]
            # Now we have finished iterating, process leftover rectangles.
            # 4. pop (x=2,h=2), max_area still = 2
            # 5. pop (x=0,h=1), max area is now (3-0)*1 = 3
            max_area = 0
            if not heights:
                return 0
            stack = [(0, heights[0])] # tuple of x_coord, height
            for j, height in enumerate(heights[1:]):
                i = j + 1
                left_x = i
                while stack and height < stack[-1][1]: # if rectangle to be added is smaller than top of stack keep popping
                    left_x, left_height = stack.pop()
                    max_area = max(max_area, (i - left_x) * left_height)
                stack.append((left_x,height)) 
                # smaller block starts from coordinate of larger one
                # so if we popped something, we use the x_coordinate of the popped thing as the new x_coord to store in the stack
                # otherwise if we didnt pop anything the new rectangle starts from this x_coord.
            total_len = len(heights)
            
            # Process any leftover rectangles after iterating thru all heights
            while stack:
                left_x, left_height = stack.pop()
                max_area = max(max_area, (total_len - left_x) * left_height)
            return max_area
                
    

Log in to reply
 

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