Google : 求柱状统计图里最大矩形面积

就是给一个柱状统计图，各个小矩形宽度相等，高度不一，每一个矩形是由几个相邻柱状条条组成，矩形的高度为最短的那根条条，求所有组合中最大的矩形面积，假设柱状统计图是放在数组里的，数组记录的是每个条条的高度。

有O(n^2), O(nlogn)和O(n)三种解法，很好的一题

见过这题，可以把高度依次压入栈中，如果当前高度小于栈顶元素，就弹出栈顶元素直到栈顶小于等于当前高度，这一过程中不断更新最大值，是可以做到O(n)的。

见过这题，可以把高度依次压入栈中，如果当前高度小于栈顶元素，就弹出栈顶元素直到栈顶小于等于当前高度，这一过程中不断更新最大值，是可以做到O(n)的。
darksteel 发表于 2011-6-6 12:08

    我觉得你已经成仙了，做了多少题老实交代

代码应该好理解：

//O(nlog(n)) solution is like quick sort ,
//O(n) solution is like to calculate the smaller closest previous index for each element

int CalcHistogram1(int a[], int n)
{
        assert(NULL != a);
        if(0 == n) return 0;

        assert(n > 0);

        //Find the smallest element
        int nSmallest = 0;
        for (int i = 0; i < n; i++)
        {
                assert(a[i] >= 0);
                nSmallest = a[nSmallest] < a[i] ? nSmallest : i;
        }

        int nRet = a[nSmallest] * n;
        int nLft = CalcHistogram1(a, nSmallest);
        int nRgt = CalcHistogram1(a+nSmallest+1, n-nSmallest-1);

        nRet = nRet > nLft ? nRet : nLft;
        nRet = nRet > nRgt ? nRet : nRgt;

        return nRet;
}

int CalcHistogram2(int a[], int n)
{
        assert(NULL != a);
        assert(n > 0);

        int nRet = 0;
        stack<int> stk;
        stk.push(0);

        for (int i = 1; i < n; i++)
        {
                assert(a[i] >= 0);
                if (a[i] >= stk.top())
                {
                        stk.push(a[i]);
                        continue;
                }

                while (!stk.empty() && stk.top() > a[i])
                {
                        int nTop = stk.top();
                        stk.pop();

                        nRet = nRet > (i-nTop)*a[nTop] ? nRet : (i-nTop)*a[nTop];
                }
        }

        int nEnd = stk.top()+1;
        while (!stk.empty())
        {
                int nTop = stk.top();
                stk.pop();

                nRet = nRet > (nEnd-nTop)*a[nTop] ? nRet : (nEnd-nTop)*a[nTop];
        }

        return nRet;
}