Largest Rectangle in Histogram
Find the largest rectangle that fits under adjacent unit-width histogram bars.
Work through the cases
3 examplesInput notation
Nonnegative heights separated by spaces.Expected result
The maximum rectangle area.Case 1
Input
2 1 4 5 1
Expected output
8
Case 2
Input
3 3
Expected output
6
Case 3
Input
0
Expected output
0
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
The first idea is enumerate every interval [l, r], take the min height, area (r - l + 1) × \min. Correct, but O(n^2). n ≤ 10^5 will time out. The bottleneck is recomputing the min over every range. Flip the enumeration: let bar i be the shortest bar of the rectangle; the width is the span to the nearest strictly shorter bars on both sides. “Nearest smaller on left/right” is the monotonic-stack model. Indices in the stack have increasing heights; a shorter bar pops others and becomes their right bound, while the new top is the left bound. Each bar enters and leaves once, so one linear pass.
We can enumerate the height h of each bar as the height of the rectangle. Using a monotonic stack, we find the index left_i, right_i of the first bar with a height less than h to the left and right. The area of the rectangle at this time is h × (right_i-left_i-1). We can find the maximum value.
The time complexity is O(n), and the space complexity is O(n). Here, n represents the length of heights.
Common model of monotonic stack: Find the nearest number to the left/right of each number that is larger/smaller than it. Template:
python stk = [] for i in range(n): while stk and check(stk[-1], i): stk.pop() stk.append(i)
class Solution {
public int largestRectangleArea(int[] heights) {
int res = 0, n = heights.length;
Deque<Integer> stk = new ArrayDeque<>();
int[] left = new int[n];
int[] right = new int[n];
Arrays.fill(right, n);
for (int i = 0; i < n; ++i) {
while (!stk.isEmpty() && heights[stk.peek()] >= heights[i]) {
right[stk.pop()] = i;
}
left[i] = stk.isEmpty() ? -1 : stk.peek();
stk.push(i);
}
for (int i = 0; i < n; ++i) {
res = Math.max(res, heights[i] * (right[i] - left[i] - 1));
}
return res;
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.