You are given an array heights describing a histogram: bar i has width 1 and height heights[i], and the bars stand side by side. Return the area of the largest rectangle that fits entirely inside the histogram.
- 1 <= heights.length <= 10^5
- 0 <= heights[i] <= 10^4
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force tries every pair of left and right ends and multiplies by the minimum height in between: O(n^2) even with a running minimum. Flip the view: every optimal rectangle has some bar as its shortest bar, and that rectangle extends to the nearest shorter bar on each side. A monotonic increasing stack finds both boundaries for free. When the current bar is shorter than the top, the top cannot extend further right; its left boundary is the index below it on the stack. Adding a height-0 bar at the end flushes everything out.
Algorithm
- Create an empty stack of indices and
best = 0. - Loop
ifrom 0 ton, using height 0 wheni == nas a sentinel. - While the stack is not empty and the current height is below
heights[top], poptopwith heighth. - Width is
iif the stack is now empty, otherwisei - stack.top - 1; updatebestwithh * width. - Push
iand continue; returnbest.
O(n)Space: O(n)class Solution: def largestRectangleArea(self, heights: List[int]) -> int: n = len(heights) stack = [] # indices, heights increasing best = 0 for i in range(n + 1): cur = 0 if i == n else heights[i] # height 0 flushes the stack while stack and cur < heights[stack[-1]]: h = heights[stack.pop()] width = i if not stack else i - stack[-1] - 1 best = max(best, h * width) stack.append(i) return best