# Python stack solution with detailed comments

• 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

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