# [leetcode] Largest Rectangle in Histogram

### Largest Rectangle in Histogram

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.

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 height = `[2,1,5,6,2,3]`,
return `10`.

tag: array, stack

C++:

```class Solution {
public:
int largestRectangleArea(vector<int> &height) {
stack<int> s;
int i = 0;
int maxArea = 0;
if(height.empty()){
return 0;
}
while(i < height.size()){
if(s.empty() || height[s.top()] <= height[i]){
s.push(i);
i++;
}
//s is not empty, height[i] < height[s.top()]
else{
int t = s.top();
s.pop();
int start = s.empty()?-1:s.top();
int thisArea = height[t] * (i - start - 1);
maxArea = max(thisArea, maxArea);
}
}
//i at the (end + 1) position of vector
while(!s.empty()){
int t = s.top();
s.pop();
int start = s.empty()?-1:s.top();
int thisArea = height[t] * (height.size() - start - 1);
maxArea = max(thisArea, maxArea);
}
return maxArea;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.