2013年09月03日

柱状图中找最大的矩形


此题在陈利人老师微薄看到,题目描述如下:

在柱状图中找到最大的矩形:给一组非负的整数来表示一个柱状图,设计一个算法找到最大面积的能适合到柱状图内的矩形。比如,对于这组数,1 2 3 4 1,有两种可能的方案,一种是适合到2 3 4内的矩形,面积是23;另一种是适合到3 4内的矩形,面积是32.你觉的能有O(n)算法没?

初次看此题目,可能不是很明白,现在贴张图在下,看着就清楚题目的意思了。

题目展示图

分析

以上面图中给出的数据为例,最大的矩形是浅黄的矩形,3*5的大小,这个结果可以一眼就从图中扫出来。当遇到程序时,这要找到一个合理的判断过程,一步步来求解出最大的矩形面积。

从左至右开始看,首先是数字1,以1为高度的矩形,长度最大可以达到图的末尾,其矩形的面积为1*9=9。 其次是数字2,以2为高度的矩形,长度最大为7,则矩形面积为2*7=14。 再次是数字3,以3为高度的矩形,长度最大是5,则矩形面积为3*5=15。 接着数字4,数字4之后就被下一个数字断开了,长度最大为1,则矩形面积为 4*1=4 。

后面接着数字3,小于上一个数字4,但与上上个数字一样大。 依次类推。

观察这个过程,如果要在O(n)的时间内找到最大的面积,则需要记录下来每个高度为N的矩形,其长度最大可以达到多少。这样就分为两种情况,如图中描述的,首先是高度N越来越大,其次是高度N越来越小。

1.在高度N越来越大时,其上一个数字构成的高度的矩形的最大长度则增加1,例如,2 3,高度为3时,则高度为2的矩形的长度就加1. 2.在高度N越来越小时,其上一个数字构成的高度的矩形的最大长度就不变,例如 4 3,高度为4时,其构成的矩形长度为1,到了3,矩形长度没有递增,而4之前的数字3构成的矩形的长度也加1。

有了上面这两条分析,就可以使用一个stack来存储矩形的高度和长度,其中长度会动态的变化。当遇到一个数字大于栈顶数字的时候就压入栈,小于栈顶的数字就弹出栈,在这个动态过程中,更新最大的矩形面积。

代码

#include<iostream>
#include<iterator>
#include<stack>

using namespace std;

void print(stack<pair<int,int> > mstack){
    while(!mstack.empty()){
        cout << "<" << mstack.top().first << "," << mstack.top().second << ">" << endl;
        mstack.pop();
    }
}

int maxrectangle(int *array, int len){
    if(array == NULL || len <= 0)
        return 0;
    stack<pair<int,int> > mstack;
    int top = 0,max = 0;
    int i = 0;
    while(i < len){
        if(array[i] > top){
            mstack.push(make_pair(array[i],1));
        }else{
            int pre = 0;
            while(array[i] < top){
                int time = mstack.top().second;
                pre += time;
                max = top*pre > max ? top*pre : max;
                mstack.pop();
                if(!mstack.empty())
                    top = mstack.top().first;
                else
                    break;
            }
            if(!mstack.empty() && mstack.top().first == array[i])
                mstack.top().second += pre+1;
            else{
                mstack.push(make_pair(array[i],pre+1));
            }
        }
        print(mstack);
        cout << "***********" << endl;
        top = mstack.top().first;
        ++i;
    }

    return max;
}

void test(int *array, int len){
    cout << "max:" << maxrectangle(array,len) << endl;
}

int main(){
    int array[] = {1,2,3,4,3,4,3,2,1};
    //int array[] = {1,2,3,4,1};
    int len = sizeof(array) / sizeof(int);
    copy(array,array+len,ostream_iterator<int,char>(cout," "));
    cout << endl;
    test(array,len);
    return 0;
}

输出结果为:

1 2 3 4 3 4 3 2 1 
<1,1>
***********
<2,1>
<1,1>
***********
<3,1>
<2,1>
<1,1>
***********
<4,1>
<3,1>
<2,1>
<1,1>
***********
<3,3>
<2,1>
<1,1>
***********
<4,1>
<3,3>
<2,1>
<1,1>
***********
<3,5>
<2,1>
<1,1>
***********
<2,7>
<1,1>
***********
<1,9>
***********
max:15

总结

整个过程需要对数据进行压栈入栈操作,故复杂度在O(n),空间复杂度也是O(n)。

这个题是在陈老师微薄上看到的,这个题是另一个题的简单版,复杂的题是在在一个位图中找到面积最大的白色矩形:给一个N*N的黑白位图,找一个面积最大的全白色的矩形。

根据上面的思路,这个求最大的白色矩阵的思路应该是一行一行的来处理。譬如,从第一行开始,从该矩阵中构造出柱状图的数组来,然后根据上面的思路来得出当前的最大值,然后从第二行开始,又重复上面的操作。最样可以在O(n)的空间下,O(nn)的时间复杂度下解决问题,当然还可以用o(nn)的空间,一次就构造出每行出发所生成的柱状图的数组来。但是没有减少复杂度。

前一篇: Openstack Network学习(四) 后一篇: 待字闺中之数组统计