本文共 1432 字，大约阅读时间需要 4 分钟。

这个问题也有动态规划子问题的属性，先来看看我们最先想到的问题的解法，矩形面积，就是底乘高了，每个点 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
   
     &height) {        int len = height.size();        int max = 0;        if(len == 0) return 0;        vector
    
      lb(len, 0);        vector
     
       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;    }};
     
    
   

转载地址：http://krlji.baihongyu.com/