Largest Rectangle in Histogram
Hard · rating 2050 · Stack
The first line contains n. The second line has n non-negative integers, the bar heights of a histogram (each bar width 1). Print the area of the largest axis-aligned rectangle that fits under the bars.
Constraints: 1 ≤ n ≤ 105, 0 ≤ hi ≤ 109
Editorial
Approach
Use a stack of bar indices with strictly increasing heights. When a shorter bar appears, the taller bars on the stack can't extend past it — pop each, and the moment you pop a bar you know its full left and right span, so you can compute the rectangle it anchors.
The sentinel
Appending a height of 0 at the end forces every remaining bar to be popped and measured.
heights.append(0); stack = []; best = 0
for i, h in enumerate(heights):
while stack and heights[stack[-1]] >= h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
best = max(best, height * width)
stack.append(i)Complexity
Time: O(n). Space: O(n).
Related problems
- Next Greater Element — Medium
- Balanced Brackets — Medium
- Maximum Nesting Depth — Medium
- Valid Parentheses — Medium