The challenge
Return the largest rectangular area beneath a histogram of unit-width bars.
Nonnegative integer heights. An empty histogram returns 0.
Example
[2,1,5,6,2,3] → 10.
Use the walkthrough below to inspect the input and each state change.
See Largest Rectangle in a Histogram, step by step
Inspect each push, pop, and recorded answer. Entries such as 2: 5 mean index: value.
Zero-based input · top labeled explicitlyLIFO
- Current input index
- —
- Main stack size
- 0
Step 01 / 15
Start with an empty stack
Read the input in order. The stack keeps only the state needed to resolve the next item.
Answer so far
Not recorded yet
- Main stack · bottom → top
- Empty
- Auxiliary stack · bottom → top
- Empty
View exact input and state
Input: [2,1,5,6,2,3]
Main stack: []. Auxiliary stack · bottom → top: [].
Put it into code
Pop a taller bar and measure width between its smaller boundaries.
Indices are zero-based. C++ uses C++17 or later.
def histogram(heights):
stack, best = [], 0
for i in range(len(heights) + 1):
height = heights[i] if i < len(heights) else 0
while stack and heights[stack[-1]] > height:
j = stack.pop()
left = stack[-1] if stack else -1
best = max(best, heights[j] * (i - left - 1))
if i < len(heights): stack.append(i)
return best
def solve(heights):
return histogram(heights)
#include <algorithm>
#include <optional>
#include <utility>
#include <string>
#include <vector>
using namespace std;
long long histogram(const vector<int>& heights) {
vector<int> stack;
long long best = 0;
int n = static_cast<int>(heights.size());
for (int i = 0; i <= n; ++i) {
int height = i < n ? heights[i] : 0;
while (!stack.empty() && heights[stack.back()] > height) {
int j = stack.back(); stack.pop_back();
int left = stack.empty() ? -1 : stack.back();
best = max(best, 1LL * heights[j] * (i - left - 1));
}
if (i < n) stack.push_back(i);
}
return best;
}
long long solve(const vector<int>& heights) { return histogram(heights); }