How do you find the largest rectangle that fits inside a histogram?
Each bar is a candidate height for a rectangle. The best rectangle for a given bar is the widest span around it where every bar is at least as tall as it, and the answer is the largest of those areas.
def largest_rectangle(heights):
stack = []
best = 0
for i, height in enumerate(heights + [0]):
while stack and heights[stack[-1]] > height:
h = heights[stack.pop()]
left = stack[-1] if stack else -1
width = i - left - 1
best = max(best, h * width)
stack.append(i)
return best
print(largest_rectangle([2, 1, 5, 6, 2, 3]))
print(largest_rectangle([2, 4]))The outputs are 10 and 4. In the first array the two bars of height five and six form a rectangle two wide and five high, which is ten, and no other rectangle is larger. In the second array the best is the single bar of height four.
The efficient way to find those spans is a monotonic stack. Keep the indices of bars in decreasing height. When a shorter bar arrives, the taller bars on top of the stack can no longer extend to the right, so pop them. For each popped bar, the nearest shorter bar to the left is the new top of the stack, and the current position is the nearest shorter bar to the right, so the span between them is the widest rectangle at that height.
The mechanism is that the stack is exactly the set of bars that could still extend rightwards, and popping one gives you both boundaries at once. The height of the popped bar is the minimum over that span, so the area is the height times the width.
The trade-off to name is against the brute force version, which tries every pair of boundaries and takes the minimum height in between, which is cubic. The stack version is linear because each index is pushed once and popped once. The sentinel also matters: appending a zero height bar at the end forces every bar still on the stack to be popped and considered, because a bar of zero height ends every rectangle that could still grow.