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)] # tuple of x_coord, height for j, height in enumerate(heights[1:]): i = j + 1 left_x = i while stack and height < stack[-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
Python stack solution with detailed comments
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.