```
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
vector<int> left(n);
vector<int> right(n);
int i;
for(i=0; i<n; i++)
{
left[i]=i-1;
right[i]=i+1;
}
for(i=0; i<n; i++)
{
while(left[i]>=0 && heights[i]<=heights[left[i]])
left[i] = left[left[i]];
}
for(i=n-1; i>=0; i--)
{
while(right[i]<n && heights[i]<=heights[right[i]])
right[i] = right[right[i]];
}
int result = 0;
for(i=0; i<n; i++)
result = max(result, (right[i]-left[i]-1)*heights[i]);
return result;
}
};
```