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

``````
class Solution {
public:
int largestRectangleArea(vector&lt;int&gt;&amp; heights) {
int lp = 0, rp = 0;
int length = 0;
int max = 0;
for(int i = 0; i &lt; heights.size(); ++i)
{
if(i &gt; 0 &amp;&amp; heights[i] == heights[i - 1]) continue;
if(heights[i] &gt; 0)
{
length = 1;
lp = i - 1;
rp = i + 1;
while(lp &gt;= 0 &amp;&amp; heights[lp] &gt;= heights[i]) { --lp; ++length; }
while(rp &lt; heights.size() &amp;&amp; heights[rp] &gt;= heights[i]) { ++rp; ++length; }
if(max &lt; heights[i] * length) max = heights[i] * length;
}
}
return max;
}
};
TLE
``````

``````
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int length = 0;
int max = 0;
for(int i = 0; i < heights.size(); ++i)
{
if(i < heights.size() - 1 && heights[i] <= heights[i + 1]) continue;
int tempMax = heights[i], minHeight = heights[i];
for(int j = i - 1; j >= 0; --j)
{
minHeight = min(heights[j], minHeight);
int temp = minHeight * (i - j + 1);
if(temp > tempMax) tempMax = temp;
}
if(tempMax > max) max = tempMax;
}
return max;
}
};
AC, 16ms
``````