084 - Largest Rectangle in Histogram

Largest Rectangle in Histogram

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.
Hide Tags
Array Stack
Hide Similar Problems
(H) Maximal Rectangle

自己先做的是用一个hash表，key是高度，value是它的累计数量，和累计过最大的数量（累计过程可能被中断）。
扫描数组：
如果遇到更小的，则前面所有点的hash表里的累计数量清零，仅保留曾累积到的最大值，
    并更新起点，下次遇到更大的值，重新累计的起点从这里算起。
如果遇到更大的，从begin的地方开始，对每个高度值进行累计，更新最大值。
最后从hash表里计算出最大的面积。
验证过这个方法的答案是正确的，但是因为要不断回头对begin之后的内容进行累计，果然是超时了。

搜了一下，更好的思路是，
找到一个峰值，回头逐步向前（一定要回头到最开始，实现的时候这里出了个bug）统计峰值左边所有的面积，更新最大值，
然后找下一个峰值，累计循环到头就可以了。
这个过程实际上也是在不断回头，但是回头的总的次数要比我之前的少得多，只是在几个峰值的地方回头，所以耗时少得多。
分析的时候有想过利用峰值，但是觉得每次回头复杂度也是O(n²)，不算很好的思路，所以没有实现，现在看起来效果还是不错的。

class Solution {
public:
    int largestRectangleArea(vector<int>& height) {
        int rst=0;
        int sz = height.size();
        if(sz)
        {
            int begin=0, idx1=0;
            for( ; idx1<sz; ++idx1)
            {
                //find next peak
                while(idx1<sz-1 && height[idx1+1]>=height[idx1])
                    idx1++;
                //get max area before this peak
                int low=height[idx1];
                rst = max(low, rst);
                for(int ii=idx1-1; ii>=0 /* don't use 'begin' */; ii--)
                {
                    low = min(height[ii], low);
                    rst = max(low*(idx1-ii+1), rst);
                }
                //begin = idx1;
            }
        }
        return rst;
    }
    //------------------------- time out solution ----------------------------
    int largestRectangleArea_timeout(vector<int>& height) {
        int rst=0;
        int sz = height.size();
        if(sz)
        {
            all_stt[height[0]].accumulate=1;
            all_stt[height[0]].max=1;
            int begin = 0;
            for(int ii=1; ii<sz; ++ii)
            {
                int cur = height[ii], pre = height[ii-1];
                if(cur<=pre)
                {
                    all_stt[cur].accumulate = all_stt[pre].accumulate + 1;
                    if(all_stt[cur].max < all_stt[cur].accumulate)
                        all_stt[cur].max = all_stt[cur].accumulate;
                   
                    begin = ii;
                    for(int bb=0; bb<begin; ++bb)
                        if(cur != height[bb])
                            all_stt[height[bb]].accumulate = 0;
                }
                else
                {
                    for(int bb=begin; bb<=ii; ++bb)
                    {
                        all_stt[height[bb]].accumulate += 1;
                        if(all_stt[height[bb]].max < all_stt[height[bb]].accumulate)
                            all_stt[height[bb]].max = all_stt[height[bb]].accumulate;
                    }
                }
            }
            for(auto a : all_stt)
            {
                int area = (a.first)*(a.second.max);
                if(rst<area)
                    rst = area;
            }
        }
        return rst;
    }
private:
    typedef struct statistics{int accumulate; int max;} STT;
    unordered_map<int, STT> all_stt;};
24 ms, Time Limit Exceeded

至于用栈的方法（链接），基本想法是一样的，都是找峰值，只不过弄了个栈来把之前的元素push进去了，
这个相当之多余，只不过要访问前面的元素么，直接下标访问不就好了么，为毛要脱裤子放屁呢。。。

【补】
好吧，搞完 085 - Maximal Rectangle，用栈回头跟数组里回头还真不一样。
用数组回头的函数，在085里跑出来是68 ms，用栈的则只要20 ms。

仔细再分析了一下，用数组回头的时候，是从现在的统计到开始，
用栈则只需要一路pop那些比当前值大的就好了，所以少了相当一部分的重复计算。
这样看来，上面用数组回头的解法也可以优化掉一部分嘛！

把原来的代码改了一下，
像栈的做法一样，在尾巴上补一个0（为了处理最后一个数据，补个最小的数字），
然后向前回头的时候就遇到比峰值后面那个数字小的数字就可以不再继续了：
    int largestRectangleArea(vector<int>& height) {
        int rst=0;
        int sz = height.size();
        if(sz)
        {
            height.push_back(0);            //##> idea from solution of stack
            sz++;                           //##> idea from solution of stack
            int begin=0, idx1=0;
            for( ; idx1<sz; ++idx1)
            {
                //find next peak
                while(idx1<sz-1 && height[idx1+1]>=height[idx1])
                    idx1++;
             
                //get max area before this peak
                int low=height[idx1];
                int next=height[idx1+1];    //##> idea from solution of stack
                rst = max(low, rst);
                for(int ii=idx1-1;
                        ii>=0,              /*don't use 'begin'*/
                        height[ii]>next;    //##> idea from solution of stack
                        ii--)
                {
                    low = min(height[ii], low);
                    rst = max(low*(idx1-ii+1), rst);
                }
                //begin = idx1;
            }
        }
        return rst;
    }
虽然在这个题里的结果并没有什么不同，还是16 ms，估计只是因为测试case的复杂程度问题，
但把这个改过的函数扔到 085 里头，瞬间12 ms 啊有没有！！快过栈的20 ms 40%~
嗯，带上这个修改之后的数组解法，再一次把栈推向了脱裤子放屁的位置，哈哈。