Largest Rectangle under a Histogram
Autumn Tournament (2015)
Submission name: maxarrea.cpp
Problem summary
Columns of unit width have positive heights. Find the largest area of an axis-aligned rectangle made of whole cells and lying entirely under the skyline.
Input
N, followed by N column heights.
Output
The maximum area.
Constraints
1≤N≤1000000; 1≤height≤15000.
Worked example
Original statement sample.
Input
11 6 5 2 7 8 6 8 3 5 6 7
Output
24
Solution analysis
- For any chosen consecutive columns, the tallest rectangle spanning them has height equal to their minimum. Enumerating all intervals is quadratic. Instead determine, for each potential limiting height, how far it can extend before encountering a shorter column.
- Keep a stack of pairs(start,height) with strictly increasing heights. When height h arrives, every larger or equal stack height has just found its right boundary. Pop it and evaluate height×(currentIndex−start); carry its start leftward into the new pair. Equal heights are merged, preserving the earliest start.
- Append a conceptual height0 after the last column to close all remaining rectangles. In the sample, columns4…7 have minimum6 and width4, giving area24. The increasing stack postpones these calculations until a genuinely smaller boundary is known.
Why it works
Every popped bar can extend from its stored start through the preceding column, and a shorter current bar prevents further extension. The stored start is the earliest legal left boundary because all taller intervening bars were merged into it. A maximum rectangle has some minimum-height bar, so that bar is evaluated with at least the optimal interval width when it is popped.
Watch out. Do not use a 32-bit area. Flush the final stack using a zero sentinel. The width excludes the current shorter column.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<pair<int,int>>stack;
long long best=0;
for(int index=0;index<=n;index++){
int height=0;
if(index<n){
cin>>height;
}
int start=index;
while(!stack.empty()&&stack.back().second>=height){
auto[left,previous]=stack.back();
stack.pop_back();
best=max(best,1LL*previous*(index-left));
start=left;
}
// Carry the earliest legal left boundary through all popped bars.
stack.push_back({start,height});
}
cout<<best<<'\n';
}