Largest Rectangle in Histogram

Explanation & Solution

Description

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Input:heights = [2,1,5,6,2,3]

Output: 10

Explanation: The largest rectangle has an area of 10 units (formed by heights 5 and 6).

Constraints

1 <= heights.length <= 10^5
0 <= heights[i] <= 10^4

Approach

Stacks pattern

1. Monotonic Increasing Stack

Maintain a stack of indices in increasing order of heights
When a shorter bar is encountered, calculate areas for all taller bars on the stack

2. Process Each Bar

For each index i (including a virtual bar of height 0 at the end):
While the stack's top bar is taller than the current bar:
Pop the top index — this bar's height defines the rectangle height
Width extends from the new stack top + 1 to i - 1
If the stack is empty, the width is i (bar extends to the left edge)
Update maxArea if this area is larger
Push current index onto the stack

3. Virtual Sentinel Bar

Appending a bar of height 0 at position n forces all remaining bars to be popped and evaluated

Key Insight

Each bar is pushed and popped exactly once, so the algorithm runs in O(n) time
When a bar is popped, we know its left boundary (the new stack top) and right boundary (the current index)
This is one of the most elegant applications of a monotonic stack

Solution Code

Basic Calculator II

Decode String