题目：
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.
代码：
class Solution {
public:
int largestRectangleArea(vector<int>& height) {
int ret = ;
const size_t len = height.size();
if (!len) return len;
int *dp_left = new int[len](), *dp_right = new int[len]();
dp_left[] = ;
dp_right[len-] = len-;
// dp_left : record the left most position of height arr that the curr element can reach
for ( size_t i = ; i < len; ++i ){
int left = i;
while ( left> && height[i]<=height[left-] ) left = dp_left[left-];
dp_left[i] = left;
}
// dp_right : vice versa
for ( int i = len-; i >; --i) {
int right = i;
while ( right<len- && height[i]<=height[right+] ) right = dp_right[right+];
dp_right[i] = right;
}
// get the largest rectangle
for ( size_t i = ; i < len; ++i ) ret = std::max( ret, (dp_right[i]-dp_left[i]+)*height[i] );
delete[] dp_left;
delete[] dp_right;
return ret;
}
};
tips：
采用dp的思路，主要参考 http://www.acmerblog.com/largest-rectangle-in-histogram-6117.html
遍历三次：
1. left to right : dp_left[i]数组存放height[i]向左最多能推到哪个位置
2. right to left : dp_right[i]数组存放height[i]向右最多能推到哪个位置
注意，不论是dp_left还是dp_right存放都是height数组的绝对位置（一开始dp_right一直存放相对位置，导致不能AC）
这里虽然for循环中又有while循环，但是复杂度并不是O(n²)，原因并不是一个挨着一个跳的，而是用之前比较的结果(dp_left，dp_right)跳的。
3. 最后走一遍dp，记录最大值
==========================================
自己找虐，又去追了一下stack的解法。自己写了很久并没有通过，学习了下网上的代码。
class Solution {
public:
int largestRectangleArea(vector<int>& height) {
int ret = ;
height.push_back();
stack<int> sta;
for ( int i = ; i < height.size(); )
{
if ( sta.empty() || height[i]>height[sta.top()] )
{
sta.push(i++);
}
else
{
int tmp = sta.top();
sta.pop();
ret = std::max( ret, height[tmp]*(sta.empty() ? i:i-sta.top()- ));
}
}
return ret;
}
};
核心思想就是：维护一个递增的stack。
1. 一旦遇到不能维持递增stack的元素了，就逐个往外弹出，直到能压进去。
2. 往外弹一个元素，就意味着这个元素不能再留着了，因此就计算一下包含弹出的这个元素在内，最大的rectangle是多少。
这里可能有一个疑问：把这个元素弹出来，那万一这个元素跟后面的元素能配上，获得更大大面积了呢？
这个是不可能发生的，因为这个元素能弹出来，必然是在其后面遇上了比它小的元素（阻断了被弹出的元素与后面的联系），因此这种算法是合理的。完毕。
===============================================
第二次过这道题，只记得用递增的stack来做了。
（1）stack里面存的是元素的下标
（2）先弹出来栈顶的元素，再看新的栈顶的元素（刚弹出来的这个元素往前能推到哪里）
class Solution {
public:
int largestRectangleArea(vector<int>& height) {
if (height.size()==) return ;
height.push_back();
int ret = ;
stack<int> sta;
for ( int i=; i<height.size(); ++i )
{
if ( sta.empty() || height[sta.top()]<height[i] )
{
sta.push(i);
}
else
{
while ( !sta.empty() && height[sta.top()]>=height[i] )
{
int tmp = sta.top();
sta.pop();
if ( sta.empty() )
{
ret = max(ret, i*height[tmp]);
}
else
{
ret = max(ret, (i-sta.top()-)*height[tmp]);
}
}
sta.push(i);
}
}
return ret;
}
};