The tell: Maximal area bounded by the shortest bar in a contiguous range.
How you get there
1For each bar, the widest rectangle at its height runs until a shorter bar on either side.
2A monotonic increasing stack finds both boundaries as bars are popped.
3Append a sentinel zero so the stack fully drains at the end.
Solution
Python
def largest_rectangle_area(heights: list[int]) -> int:
heights = heights + [0] # sentinel forces the stack to drain
stack: list[int] = [] # indices, heights increasing
best = 0
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
left = stack[-1] + 1 if stack else 0
best = max(best, height * (i - left))
stack.append(i)
return best
Time
O(n)
Space
O(n)
What goes wrong
Omitting the sentinel leaves bars on the stack unprocessed when the histogram ends ascending.