Practice › Stack & Queue
Largest Rectangle in Histogram
Hard · Stack & Queue · Asked at Google, Amazon, Microsoft, Adobe
Bars of width 1 have the given heights. Print the area of the largest rectangle inside the histogram.
Input
First line: n. Second line: n heights.
Output
The largest area.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ h[i] ≤ 10^4
For each bar find the nearest smaller bar on both sides with a monotonic stack.
Example 1
Input
6 2 1 5 6 2 3
Output
10
Example 2
Input
2 2 4
Output
4
Hints
- In the best rectangle, some bar is the shortest one — and the rectangle stretches left and right until a shorter bar blocks it.
- Use a stack of increasing heights. When a shorter bar arrives, pop: the popped bar's rectangle spans from the new stack top + 1 to i − 1.
Approach
Keep a stack of indices with increasing heights. When h[i] is lower than the top, pop the top index t: bar t can't extend to i, and the bar now on top is the nearest shorter bar on its left. So its rectangle has height h[t] and width i − (newTop + 1), or i if the stack is empty. Adding a final bar of height 0 flushes the stack. Each index is pushed and popped once. Areas reach 10^9, so use 64 bits.
Complexity: O(n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> h(n);
for (auto &x : h) cin >> x;
h.push_back(0); // sentinel flushes the stack at the end
vector<int> st;
long long best = 0;
for (int i = 0; i <= n; i++) {
while (!st.empty() && h[st.back()] > h[i]) {
long long height = h[st.back()];
st.pop_back();
long long width = st.empty() ? i : i - st.back() - 1;
best = max(best, height * width);
}
st.push_back(i);
}
cout << best << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
h = data[1 : n + 1] + [0] # sentinel flushes the stack at the end
stack, best = [], 0
for i, x in enumerate(h):
while stack and h[stack[-1]] > x:
height = h[stack.pop()]
width = i - stack[-1] - 1 if stack else i
best = max(best, height * width)
stack.append(i)
print(best)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] h = new long[n + 1]; // h[n] = 0 is a sentinel
for (int i = 0; i < n; i++) h[i] = sc.nextLong();
int[] st = new int[n + 1];
int top = 0;
long best = 0;
for (int i = 0; i <= n; i++) {
while (top > 0 && h[st[top - 1]] > h[i]) {
long height = h[st[--top]];
long width = top == 0 ? i : i - st[top - 1] - 1;
best = Math.max(best, height * width);
}
st[top++] = i;
}
System.out.println(best);
}
}Solve Largest Rectangle in Histogram online · All practice problems