084.md

Largest Rectangle in Histogram

题目

  给一个数组,每个数组的值表示一个高度，如 {2,1,5,6,2,3} 表示6个底为1高分别为2,1,5,6,2,3的矩形。找出矩阵之间组合而成的最大的矩形。这里是10(5和6)   之间组合。

思路

  该算法的核心就是使用栈实现 检测有可能产生最大值的情况，排除了没有意义的检测。

  使用栈stack index。

  遍历一边数组(遍历使用的变量为i)，如果当前的情况是递增的的，也就是heights中的数据不断的增高，则将对应的索引加入到index中，   直到出现单个数据变小的情况.则处理index中heighs[index.top()] > heights[i]的数据。没处理一个索引就将该值在index中pop出来。     如{1,2,3,4,5,3···}检测到第二个3的时候，就有情况有可能产生最大值，对于高h为5(heighs[index.top()])的时候,底为5前面

  比5小的单个矩形的位置与当前i的间隔，前面比5小的矩形为4到i的间隔为1。所以有可能产生的最大值为5=5x1，对于4的情况，4的

  前一个比4小的矩形为3,则3到i的间隔为2则有可能产生的最大值为8=4x2。

  i继续向前检测，其实就是不断的检测递增的情况，递增就push索引进index中，一旦出现下降的情况如上5->3的情况，就对index中

  索引所表示的值比下降后的值(3)大的做处理，他们有可能产生最大值，即以该heights[index.top()]为高，低为两边都比他小的

  矩形的间隔。对于一直递增得话，每一个单位矩形都在"右边"找不到比他根小的矩形，所以无法决定有意义的高，所以为了算法循环

  的简洁性在给定的数组heighs的最后加上一个0.  

代码

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> index;
        //使整个循环更简洁
        heights.push_back(0);
        int n = heights.size();
        int res = 0;
        for( int i=0 ; i < n ; ++i ){
            //stack不为空的时候且当前i表示的矩形大小小于前一个矩形
            while(!index.empty() && heights[index.top()]>=heights[i]){
                int h = heights[index.top()];
                index.pop();
                //等于-1表示从第一个矩形开始到当前h表示的矩形都要穿进去
                //等于index.top()表示从比他小的一个矩型开始到当前h表示的矩形
                int left = index.empty() ? -1 : index.top() ;
                int wide = i - left -1;
                if(h*wide>res) res = h*wide;
            }
            index.push(i);
        }    
        return res;
    }
};

下面代码是一个动态规划的思路，算法是正确的，但在leetcode无法通过。卡在倒数第二个例子。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int heights_sz = heights.size();
        if(heights_sz==0) 
            return 0;
        if(heights_sz==1) 
            return heights[0];
         //0行0列不用
        vector<int> e(heights_sz+1,0);  
        vector<int> min_value(heights_sz+1);
        
        //初始化
        for(int i=1;i<=heights_sz;++i){
            e[i] = heights[i-1];
            min_value[i] = heights[i-1];
        }
        
        for(int l=2;l<=heights_sz;++l){
            for(int i=1;i<=heights_sz-l+1;++i){
                int j=i+l-1;
                min_value[i] = min(min_value[i],min_value[i+1]);
                int temp = max(e[i],e[i+1]);
                e[i] = max(temp,(j-i+1)*min_value[i]);
            }
        } 
        return e[1];
    }
};