题目描述如下：
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 height = [2,1,5,6,2,3],
return 10.
======================================================
这题刚开始脑筋转不过来，老实去想什么长跟宽的关系啊什么的，只能想到o(n2)的办法。
后来在网上看别人提示： 对一个最大面积它的高必定是某一个柱的柱高，因此我们可以枚举每一个柱高然后向左右扩展找最长的长度，扩展的条件是两边的柱高必须高于等于它。
我们使用 leftest[ ] 和 rightest[ ]来保存每个柱子最左和最右能扩展到的下标，于是对每个柱子，以其高能扩展的最大面积为： height[ i ]* ( rightest [i ] - leftest [i ] +1 )，最后返回最大的那个就是了。
简单的对每个i 向左右扩展更新 leftest 和 rightest 是O（ｎ２）的，有没有办法将其降低到 ｏ（ｎ）呢？ 当然是有的：那就是借助单调队列！
首先我们这么想，对一个ｉ，其高度为height[i]，i-1 的leftest[i-1]已经计算过了，如果height[i] 比左边高，肯定不能向左边扩展了，leftest[i] = i，如果比左边低，我们能直接说leftest[i] = leftest[i -1]吗？ 当然是不行的，比如我们举个反例：
height : 2 3 1 ： 明显leftest[0] =0 ,leftest[1]=1,此时我们发现 1<3，那我们可以得到 leftest[2]=leftest[1]=1吗？明显不是，还可以向左扩展的。
所以我们必须要找到 i 左边最远的比它大的元素，然后leftest等于它，这个过程可以借助单调队列，因为单调队列所有元素最多只进一次栈出一次栈，所以分摊复杂度是o(n)的！
单调队列我就不介绍了，各位可以在网上找些浅显的资料了解一下！
代码如下：
int largestRectangleArea(vector<int>& hei)
{
if(hei.empty())
return 0;
int sz=hei.size();
vector<int> leftest(sz,0);
vector<int> rightest(sz,0);
vector<int> lQueue;
vector<int> lIndex;
vector<int> rQueue;
vector<int> rIndex;
int i;
for(i=0;i<sz;i++)
{
if (lQueue.empty()||lQueue.back()<hei[i])
{
leftest[i]=i;
lQueue.push_back(hei[i]);
lIndex.push_back(i);
}
else
{
int tmp=i;
while(!lQueue.empty()&&lQueue.back()>=hei[i])
{
tmp=leftest[lIndex.back()];
lQueue.pop_back();
lIndex.pop_back();
}
leftest[i]=tmp;
lQueue.push_back(hei[i]);
lIndex.push_back(i);
}
}
for(i=sz-1;i>=0;i--)
{
if(rQueue.empty()||rQueue.back()<hei[i])
{
rightest[i]=i;
rQueue.push_back(hei[i]);
rIndex.push_back(i);
}
else
{
int tmp=i;
while(!rQueue.empty()&&rQueue.back()>=hei[i])
{
tmp=rightest[rIndex.back()];
rQueue.pop_back();
rIndex.pop_back();
}
rightest[i]=tmp;
rQueue.push_back(hei[i]);
rIndex.push_back(i);
}
}
int ans=INT_MIN;
for(i=0;i<sz;i++)
{
ans=max(ans,hei[i]*(rightest[i]-leftest[i]+1));
}
return ans;
}