Largest Rectangle in Histogram

LeetCode 84 • Hard • Stack

Input: heights = [2,1,5,6,2,3] → Output: 10. Monotonic stack: pop while stack top > current, area = height[pop] × width.

TimeO(n)

SpaceO(n)

i: — stack: [] maxArea: 0

Stack indices

Current area

i—

stack[]

maxArea0

Speed:

Ready

Press Play. Monotonic stack: pop while heights[stack[-1]] > heights[i]. Area = height[pop] × width.

Whiteboard

Size:3

Type It

Practice until you don't need to look. Monotonic stack: pop while top > current, area = h × width.

═══ LARGEST RECTANGLE — MONOTONIC STACK ═══

PATTERN ▸ Monotonic stack (indices, increasing) O(n) · O(n)

① INIT

stack, max_area = [], 0

② FOR i IN RANGE(n+1)

h = heights[i] if i<n else 0

while stack and heights[stack[-1]] > h:

idx = stack.pop(); w = i - stack[-1] - 1 if stack else i

max_area = max(max_area, heights[idx] * w)

stack.append(i)

③ RETURN

return max_area

your implementation

Verify: