#84
Largest Rectangle in Histogram
Hard Monotonic stack
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Bars of width 1 have given heights. Return the area of the largest rectangle that fits inside the histogram.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the largest rectangle inside the bars.
Why this works: each bar's best rectangle stretches until a shorter bar on each side. An increasing stack finds both sides when a bar is popped.
Example: [2, 1, 5, 6, 2, 3]
2 pops 6 → 6×1, then 5 → 5×2 = 10best 10
✦Hints open one at a time
For each bar, the widest rectangle of that height stretches until a shorter bar on each side.
An increasing stack of indexes finds both boundaries: when a bar is popped, the current index is its right boundary and the new top is its left boundary.
↗Approach
Scan i from 0 to n (with height 0 at n as a sentinel). While the current height is lower than the top's height, pop the top; width = i − newTop − 1 (or i if the stack is empty). Track the best area.
</>Solution (Java)
import java.util.*;
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length, best = 0;
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i <= n; i++) {
int h = (i == n) ? 0 : heights[i]; // sentinel bar of height 0
while (!st.isEmpty() && heights[st.peek()] > h) {
int height = heights[st.pop()];
int width = st.isEmpty() ? i : i - st.peek() - 1;
best = Math.max(best, height * width);
}
st.push(i);
}
return best;
}
}!Common mistake
Forgetting the sentinel at the end, so bars left in the stack are never measured.
Complexity
- Time: O(n).
- Space: O(n).
Topic: Stack & Queue
🎬 Episodes 46–52: video coming soon