给出按顺序放置的n个矩形,宽度为1,高度给定.这些矩形拼成了一个多边形,求其中最大的子矩形面积.

链接

POJ2559

题解

首先有个显然的结论,选择出的子矩形的高度一定和其中的某个小矩形的高度相同.

朴素的做法是枚举选择的小矩形,然后左右延伸计算最大距离能达到多少.注意到,假如说被选择的矩形左侧有一个矩形比它高,而且已知其向左最多能延伸到L的位置,那么右边的矩形向左一定可以延伸到比L更远(至少也是相同)的位置.这一结论的正确性不难证明.

于是,考虑维护一个单调栈,里面放置的是矩形的坐标,而且对应的高度是单调递增的.依次让这些矩形入栈,把栈内高度比它大的全部弹出,被弹出的矩形向右能延伸到的最远位置就是当前矩形的前一个位置.同时,这些被弹出的矩形也不断更新当前矩形向左能延伸到的最远位置.最后有个细节是要加入一个高度为-1的矩形,这样保证最后插入完毕后栈里的矩形的右延伸距离能得到更新.总的时间复杂度是

O(n)

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<stack>
#define N 100010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,i;
LL Ans;
LL a[N],l[N],r[N];

stack <int> Q;

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline LL Max(LL a,LL b){return (a>b)?a:b;}

inline LL read(){
    LL p=0; char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    while (1){
        n=read();
        if (!n) break;
        for (i=1;i<=n;i++)  a[i]=read();
        while (!Q.empty())  Q.pop();
        a[++n]=-1;
        for (i=1;i<=n;i++){
            l[i]=r[i]=i;
            while (!Q.empty()&&a[Q.top()]>a[i]){
                l[i]=l[Q.top()];
                r[Q.top()]=i-1;
                Q.pop();
            }
            if (!Q.empty()&&a[Q.top()]==a[i])   l[i]=l[Q.top()];
            Q.push(i);
        }
        Ans=0;
        for (i=1;i<=n;i++)  Ans=Max(Ans,(r[i]-l[i]+1)*a[i]);
        //for (i=1;i<=n;i++)    cout<<l[i]<<" "<<r[i]<<endl;
        printf("%lld\n",Ans);
    }
    return 0;
}