首页 > 代码库 > hdu 1506 Largest Rectangle in a Histogram 单调栈

hdu 1506 Largest Rectangle in a Histogram 单调栈

 

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int a[100100],q[100100],l[100100],r[100100];int main(){    int i,n,cnt;    while(scanf("%d",&n),n!=0)    {        for(i=1;i<=n;i++)        {            scanf("%d",&a[i]);            l[i]=1;            r[i]=n;        }        cnt=0;        for(i=1;i<=n;i++)        {            while(cnt&&a[ q[cnt] ]>a[i])            {                r[q[cnt]]=i-1;                cnt--;            }            q[++cnt]=i;        }        cnt=0;        for(i=n;i>=1;i--)        {            while(cnt&&a[ q[cnt] ]>a[i])            {                l[q[cnt]]=i+1;                cnt--;            }            q[++cnt]=i;        }        //for(i=1;i<=n;i++)          //  printf("%d %d\n",l[i],r[i]);        __int64 ans=0;        for(i=1;i<=n;i++)            ans=max(ans,(__int64)a[i]*(r[i]-l[i]+1));        printf("%I64d\n",ans);    }    return 0;}

 

hdu 1506 Largest Rectangle in a Histogram 单调栈