How do you find the largest rectangle that fits inside a histogram?
You keep a stack of the bars that are still waiting, and when a shorter bar arrives the bars that are taller than it have found their limit, so you work out their rectangles.
def largest_rectangle(heights):
stack = []
best = 0
for i, height in enumerate(heights + [0]):
while stack and heights[stack[-1]] > height:
top = stack.pop()
left = stack[-1] if stack else -1
width = i - left - 1
area = heights[top] * width
if area > best:
best = area
stack.append(i)
return best
So how does it work? A rectangle in a histogram is a rectangle that sits on the bottom and covers a set of neighbouring bars, and its height cannot be more than the shortest bar that it covers. So for every bar you want to know how wide a rectangle you could build with that bar as the shortest one.
And the stack helps you find that. The stack holds the bars that are still waiting, and it is increasing from the bottom to the top. When the current bar is shorter than the bar on top of the stack, that top bar cannot be the shortest of a rectangle that includes the current bar, so its rectangle has to end just before the current bar.
the heights the stack after each bar
-------------- ----------------------
[2, 1, 5] [0]
[2, 1, 5] [0, 1]
[2, 1, 5] [0, 1, 2]
the extra 0 at the end pops them all
And the width comes from the stack itself. The left edge of the rectangle is the bar under the popped one, and the right edge is the current position minus one. So the width is i - left - 1, where left is the position under the popped bar or minus one if there is nothing under it.
And the extra zero at the end of the list is what makes it work. The zero is shorter than every bar, so when you reach it every waiting bar is popped and gets its area worked out. Without it the bars that are still waiting at the end would never be counted.
And the complexity is O of n for the time, because every bar goes on the stack once and comes off once, and O of n for the space.
So the rule to remember is this. When a bar is popped, the stack tells you the width and the bar tells you the height.
The last question in this topic also gives you the boundaries.