Largest Rectangle in Histogram 1 : 4 * 4 = 16 units. Largest Rectangle in Histogram 2 : 2 * 6 = 12 units.
The idea behind this algorithm is: 1. For each bar do the following
a) If the height of the current bar is greater than the height of the previous bar, - Store the current bar’s height and the position in their respective stacks. Else if the height of the current bar is less than the height of the previous bar - Find the area of the largest rectangle that can be formed using the heights and the positions stored in the stack. - Pop-out the height and the position of each bar from the stack while calculating the area of the rectangle. - Continue finding the area using the heights stored in the stack that are greater than the current bar’s height. - Push the height of the current bar into the height stack and the position of the previously removed bar. 2. While the height stack is not empty - Find the area of the rectangle that can be formed using the histogram size, heights and the positions stored in the stack. - Pop-out the height and the position of each bar from the stack while calculating the area of the rectangle. - If the calculated area is greater than the earlier calculated areas, the largest rectangle is the newly found rectangle.
Data structure used : Stack(s). One stack is used for storing the height and the other is used for storing the indices of the bars. Time Complexity : O(n), where n is the number of bars in histograms.
C++14 Finding the largest rectangle in the historgram.
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
typedef vector<int> VI;
typedef stack<int> SI;
int GetArea(vector<int> histogram){
int sz = histogram.size();
stack<int> stack_of_height, stack_of_position;
int area=0;
int index=0,height=1;
for(int pos=0; pos<sz; pos++){
// If the height of the current bar is greater than the height
// at the top of stack push it.
if( stack_of_height.empty() || stack_of_height.top() < histogram[pos] ){
stack_of_height.push(histogram[pos]);
stack_of_position.push(pos);
} else {
if( stack_of_height.top() > histogram[pos] ){
// If the height of the current bar is less than the height at the top of
// the stack, pop out all the bigger heights and their corresponding positions
// and find the maximum area.
while( !stack_of_height.empty() && stack_of_height.top() > histogram[pos] ){
index = stack_of_position.top();
stack_of_position.pop();
height = stack_of_height.top();
stack_of_height.pop();
area = max(area, height * (pos-index));
}
// Note: We are pushing height of the current bar and the position of the last removed
// index.
stack_of_height.push(histogram[pos]);
stack_of_position.push(index);
}
}
}
while(!stack_of_height.empty()){
int tempArea = stack_of_height.top() * (histogram.size() - stack_of_position.top());
stack_of_height.pop();
stack_of_position.pop();
if(tempArea > area){
area = tempArea;
}
}
return area;
}
int main(){
vector<int> vec1 = {6, 2, 5, 4, 5, 1, 6}; // 12
cout << "Histogram {6, 2, 5, 4, 5, 1, 6} : " << GetArea(vec1) << endl;
vector<int> vec2 = {6}; // 6
cout << "Histogram {6} : " << GetArea(vec2) << endl;
vector<int> vec3 = {7, 2, 1, 4, 5, 1, 3, 3}; // 8
cout << "Histogram {7, 2, 1, 4, 5, 1, 3, 3} : " << GetArea(vec3) << endl;
vector<int> vec4 = {4, 1000, 1000, 1000, 1000}; // 4000
cout << "Histogram {4, 1000, 1000, 1000, 1000} : " << GetArea(vec4) << endl;
vector<int> vec5 = { 1000, 1000, 1000, 1000}; // 4000
cout << "Histogram { 1000, 1000, 1000, 1000} : " << GetArea(vec5) << endl;
vector<int> vec6 = {2, 3, 4, 5, 5, 4, 3, 2}; // 18
cout << "Histogram {2, 3, 4, 5, 5, 4, 3, 2} : " << GetArea(vec6) << endl;
vector<int> vec7 = {5, 5, 5, 5, 5}; // 25
cout << "Histogram {5, 5, 5, 5, 5} : " << GetArea(vec7) << endl;
return 0;
}
Output
Histogram {6, 2, 5, 4, 5, 1, 6} : 12
Histogram {6} : 6
Histogram {7, 2, 1, 4, 5, 1, 3, 3} : 8
Histogram {4, 1000, 1000, 1000, 1000} : 4000
Histogram { 1000, 1000, 1000, 1000} : 4000
Histogram {2, 3, 4, 5, 5, 4, 3, 2} : 18
Histogram {5, 5, 5, 5, 5} : 25