Given an array of bar heights representing a histogram, find the area of the largest rectangle that can be formed within the histogram.
heights = [2, 1, 5, 6, 2, 3]
#
# ┌──┐
# ┌──┤ │
# │ │ │ ┌──┐
# ┌──┐ │ │ │ ┌──┤ │
# │ │ │ │ │ │ │ │
# └──┴──┴──┴──┴──┴──┴──┘
# 2 1 5 6 2 3
# Largest rectangle: width=2 × height=5 = 10
# (bars at index 2,3 with heights 5,6 → min height 5)
This is a classic monotonic stack problem:
This is considered one of the hardest stack problems. It combines monotonic stacks with clever width calculation.
📋 Instructions
Implement `largest_rectangle(heights)` using a monotonic stack.
Test with [2,1,5,6,2,3].
Use a stack of (index, height). When you find a shorter bar, pop taller bars and calculate area = height * (current_i - popped_index). Push the current bar with the leftmost valid start index. At end, process remaining stack entries with width extending to end.