The biggest rectangle in a bar chart
Find the largest rectangle that fits under a bar chart, by popping each bar when a lower bar arrives and measuring how far it could stretch. About 20 minutes.
A bar stretches until a lower one
Given bars of various heights, a rectangle of height h can use any run of bars that are all at least h tall. For each bar, the widest rectangle of its own height stretches left and right until it meets a bar that is lower.
Keep a stack of bars in rising order. While the new bar is no lower than the top, just push. A lower bar arrives, and that is the moment the top bar's right edge is known.
while stack and h[stack[-1]] >= cur:
height = h[stack.pop()]Bar 1 is lower than bar 0 (height 2). Pop it: width 1, area 2. Push bar 1.
Measure at the pop
When you pop a bar, the bar now on top of the stack is the nearest lower bar on its left, and the current position is the nearest lower bar on its right. The width in between is the current position minus that left position minus one.
If the stack is empty, nothing on the left is lower, and the left edge is position minus one. Add a bar of height 0 after the end so that every remaining bar gets popped and measured.
left = stack[-1] if stack else -1 best = max(best, height * (i - left - 1))
Bars are 3, 3, 3. What is the largest rectangle?
- A9
- B3
- C6
Show the answer
9. All three bars are at least 3 tall, so the rectangle is 3 wide and 3 tall.
Largest rectangle in histogram
You are given an array heights, the heights of bars in a histogram, where every bar has width 1. Return the area of the largest rectangle that can be drawn inside the histogram.
heights = [2, 1, 5, 6, 2, 3] → 10
1 ≤ length of heights ≤ 100,000 · 0 ≤ heights[i] ≤ 10,000