这个问题也有动态规划子问题的属性，先来看看我们最先想到的问题的解法，矩形面积，就是底乘高了，每个点 i 都有一个“高”值保存，那么能以这个高为高的底是什么呢？当然就是在其左右的，连续的，高度都至少跟自己"高”值相等的点所构成的点序列的长度，这就是所谓的见贤思齐，你周围人的高度，决定你自己的“高度”，道理都是相同的，O(∩_∩)O~
那子问题体现在哪呢？我们想要一种这样的结果，比如1,1,1,2,3,4,5,6，4，我们在判断第二个4的左边比其本身大的那些点的时候，我们其实走到第一个4就可以了，就不用再往前比了，我们希望第一个4的位置会提供给我们信息，所以我们就需要记录一下每个点的一些信息，什么信息呢，通过上面的分析，我们最需要的应该是边界信息，比如这里所说的左边界，就是在我的左边，比我大的元素的下标，对称的，我们要记录右边界。那么最后，对于第i个高度a[i], 向左找到左边界（最后那个不小于它的），向右找到右边界，那么，根据木桶原理，最矮的a[i]的高度就决定了最终的面积，求出每个a[i]的左l[i],r[i]边界后，result = max { area[i] | area[i] = (r[i] - l[i] + 1)*height[i]}
class Solution {
public:
int largestRectangleArea(vector<int> &height) {
int len = height.size();
int max = 0;
if(len == 0) return 0;
vector<int> lb(len, 0);
vector<int> rb(len, 0);
lb[0] = 0;
rb[len - 1] = len - 1;
for(int i = 1; i < len; ++i)//left bounder of every item.
{
int cur = i;
while(cur > 0 && height[i] <= height[cur - 1]) cur = lb[cur - 1];
lb[i] = cur;
}
for(int i = len - 1; i >= 0; --i)//right bounder of every item.
{
int cur = i;
while(cur < len - 1 && height[i] <= height[cur + 1]) cur = rb[cur + 1];
rb[i] = cur;
}
for(int i = 0; i < len; ++i)//find the max area.
{
int area = (rb[i] - lb[i] + 1) * height[i];
if(area > max) max = area;
}
return max;
}
};