# 84.Largest Rectangle in Histogram

Givennnon-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. Above is a histogram where width of each bar is 1, given height =`[2,1,5,6,2,3]`. The largest rectangle is shown in the shaded area, which has area =`10`unit.

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

Thoughts:

1. have a stack to record increasing index
2. while current index is less that the top of the stack, update the maximum area
3. having a increasing stack is because as index gets larger, the only possible way for rectangle starting from larger index is due to its larger height value.

Code time complexity: O(n), space complexity: O(n)

``````class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> s;
s.push(-1);
int ans = 0;
int n = heights.size();
for(int i = 0; i < n; i++){
while((s.top()!= -1) && heights[s.top()] >= heights[i]){
int last_idx = s.top(); s.pop();
ans = max(ans, heights[last_idx] * (i - s.top() - 1));
}
s.push(i);
}
// reach the end of list
while(s.top()!= -1){
int last_idx = s.top(); s.pop();
ans = max(ans, (heights[last_idx]) * (n - 1 - s.top()));
}

return ans;
}
};
``````

Code using 0 padding at the end and vector as stack

`````` class Solution {
public:
int largestRectangleArea(vector<int> &height) {

int ret = 0;
height.push_back(0);
vector<int> index;

for(int i = 0; i < height.size(); i++)
{
while(index.size() > 0 && height[index.back()] >= height[i])
{
int h = height[index.back()];
index.pop_back();

int sidx = index.size() > 0 ? index.back() : -1;
if(h * (i-sidx-1) > ret)
ret = h * (i-sidx-1);
}
index.push_back(i);
}

return ret;
}
};
``````

Special thanks to sipiprotoss5's for the last solution