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.
Below 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 =10unit.
For example,
Given heights =[2,1,5,6,2,3],
return10.
My solution used the monotone stack with time complexity O(N).
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
if(heights.size() == 0) return 0;
heights.push_back(0);
stack<int> myStack;
int maxArea = 0;
for(int i = 0; i < heights.size(); i++){
if(myStack.empty() || heights[i] > heights[myStack.top()]){
myStack.push(i);
}else{
int top = heights[myStack.top()];
myStack.pop();
int width = i - (myStack.empty() ? -1 : myStack.top()) - 1;
maxArea = max(maxArea, top*width);
i--;
}
}
return maxArea;
}
};
