Billchenchina 标签 联系 友链

POJ2559 Largest Rectangle in a Histogram

Posted by Billchenchina on September 18, 2017
标签: 题解 单调栈 POJ

这道题好眼熟…

igronemyk 大神犇 今年4月份蛤理工“尚学堂杯”的时候就学会了,而我现在才 AC …无限膜拜

传送门们:HRBUST POJ DBSDFZOJ1189

题意

每个木板宽度都为 1,木板按输入时顺序排列,求最大矩形面积。

基础知识

单调栈

顾名思义,单调栈,首先是一个栈,且栈内元素有单调性,单调栈的维护也很简单,只要在加入元素的时候暴力弹栈维护单调性即可。

–LZJ209

解法

大致思路

考虑到单调栈的单调性(废话),可以 以矩形的高 为顺序维护一个单调增的栈,栈内类型为pair<long long,long long>

对每次处理的情况分类讨论

  • 如果栈为空,则将pair(v[i],1)压入栈中。
  • 如果加入v[i]仍能保持单调性,则将pair(v[i],1)压入栈中。
  • 否则,弹栈至 加入v[i]时能保持单调性,再将pair(v[i],x)压入栈中。(x 为从 i 位置向左能延伸的最大宽度)

前两种情况很好处理,但第三种情况就比较难处理。求 x 的过程会增加一层复杂度,那么 x 怎么求?

求 x

懒得写了。。。见 POJ2559 最大矩形面积

高度为1的元素准备进栈,但必须从栈顶开始删除高度大于或等于1的矩形,因为2已经不可能延续到当前矩形。删除(2,1)这个元素之后,更新最大矩形面积为2*1=2,然后把它的宽度1累加到当前高度为1的准备进栈的矩形,然后进栈,当前栈为(1,2)

高度为1的元素准备进栈,删除(5,1)这个元素,更新最大矩形面积为51=5,把1累加到下一个元素,得到(4,2),删除(4,2),更新最大矩形面积为42=8,把2累加到下一个元素,得到(1,4),1*4=4<8,不必更新,删除(1,4),把4累加到当前准备进栈的元素然后进栈,当前栈为(1,5)

代码

#include <stack>
#include <iostream>
#include <vector>

using namespace std;

struct mypair
{
    int length;
    int width;
    mypair() {}
    mypair(int _length,int _width)
    {
        length=_length;
        width=_width;
    }
};
typedef mypair pint;
int main()
{
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n&&n!=0)
    {
        stack<pint>st;
        vector<long long>v(n+2);
        for(int i=1; i<=n; ++i)
        {
            cin>>v[i];
        }
        long long maxarea=-1;
        v[n+1]=0;
        for(int i=1; i<=n+1; ++i)
        {

            if(st.empty())
            {
                st.push(mypair(v[i],1));
            }
            else
            {
                if(v[i]>st.top().length)
                {
                    st.push(mypair(v[i],1));
                }
                else
                {
                    long long width=0;

                    while(!st.empty()&&st.top().length>=v[i])
                    {
                        width+=st.top().width;
                        if(width*st.top().length>maxarea)
                        {
                            maxarea=width*st.top().length;
                        }
                        st.pop();
                    }
                    st.push(mypair(v[i],width+1));
                }
            }
        }
        cout<<maxarea<<endl;
    }

}

Code