LeetCode #84

Description:

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Example:

``````Given heights = [2,1,5,6,2,3],
return 10.
``````

Time: O(n)

Code:

``````class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> s_height;
heights.push_back(0);

int max_area=0;
int i=0;
while(i<heights.size()){
if(s_height.empty()||heights[i]>heights[s_height.top()]){
s_height.push(i++);
}
else{
int indx=s_height.top();
s_height.pop();
int curr_area= heights[indx]*(s_height.empty()? i : i-s_height.top()-1);
max_area = max(curr_area, max_area);
}
}
return max_area;
}
};
``````

This version does not modify the input vector.

``````class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> s_height;

int max_area=0;
int i=0;
while(i<heights.size()){
if(s_height.empty()||heights[i]>heights[s_height.top()]){
s_height.push(i++);
}
else{
int indx=s_height.top();
s_height.pop();
int curr_area= heights[indx]*(s_height.empty()? i : i-s_height.top()-1);
max_area = max(curr_area, max_area);
}
}
// Stack is not empty, keep pop and calculate
while(!s_height.empty()){
int indx=s_height.top();
s_height.pop();
int curr_area= heights[indx]*(s_height.empty()? i : i-s_height.top()-1);
max_area = max(curr_area, max_area);
}
return max_area;
}
};
``````