> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/solutions/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/solutions/largest_rectangle_in_histogram.md).

# 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;

}