Description
Find the largest rectangular area beneath adjacent unit-width histogram bars. Heights are nonnegative; a rectangle cannot exceed any bar it crosses.
Solution
def largest_rectangle_area(heights):
stack = []
best = 0
for right in range(len(heights) + 1):
current = heights[right] if right < len(heights) else 0
while stack and heights[stack[-1]] > current:
height = heights[stack.pop()]
left = stack[-1] if stack else -1
best = max(best, height * (right - left - 1))
stack.append(right)
return bestExamples
Example 1
- Input
[[2,1,5,6,2,3]]- Output
10
Height 5 across two bars gives area 10.
Example 2
- Input
[[2,4]]- Output
4
Either two height-2 bars or one height-4 bar gives area 4.
Example 3
- Input
[[0,0]]- Output
0
Zero heights have zero area.
Approach
Keep indices of bars in increasing height order. When a shorter bar appears, pop taller bars and compute their maximal widths using the new index and the previous stack index. A final zero-height sentinel flushes the stack.
Time & space
O(n) time and O(n) auxiliary space, where n is the bar count.