Largest Rectangle in Histogram

int largestRectangleArea(vector<int>& heights) {

stack<int> s;

heights.push_back(0);

int ret = 0;

for(int i=0;i<heights.size();){

if(s.empty() || heights[s.top()]<heights[i]){

s.push(i++);

}

else{

int temp=s.top();

s.pop();

ret=max(ret,heights[temp]*(s.empty()?i:i-1-s.top()));

}

}

return ret;

}

Last updated

Was this helpful?