hdu 1506:Largest Rectangle in a Histogram 【单调栈】

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 const int N=;

 int Stack[N];    //Stack[]为单调栈（即每次能入栈的元素值必比栈顶元素（若存在）要大）

 int len[N];        //len[]与Stack[]同步 ，记录的是从Stack[]中对应元素起向左最大可延伸的宽度

 int n;

 LL top,ans,h;

 void print()

 {

     printf("top=%d,    ans=%d\n",top,ans);

     printf("\tStack:");

     for(int i=;i<=top;i++)

         printf("%6d",Stack[i]);

     puts("");

     printf("\t  len:");

     for(int i=;i<=top;i++)

         printf("%6d",len[i]);

     puts("");

 }

 int main()

 {

     while(scanf("%d",&n)&&n)

     {

         memset(Stack,,sizeof(Stack));

         memset(len,,sizeof(len));

         top=-,ans=;

         for(int i=; i<=n; i++)

         {

             if(i<n) scanf("%lld",&h);

             else h=-;    //用作结束标记

             if(top<||Stack[top]<h)

             {

                 Stack[++top]=h;    //    h入栈

                 len[top]=;        //    显然新入栈元素比原栈顶元素大，此时向左最大延伸“1”宽度

             }                    //  “1”可根据具体题目进行修改~

             else    // if(top>=0&&Stack[top]>=h

             {

                 int l=;

                 while(Stack[top]>=h&&top>=)

                 {

                     ans=max(ans,(LL)(len[top]+l)*Stack[top]);    //更新ans

                     l+=len[top--];    //Stack[]和len[]同时将栈顶元素弹出

                 }    //循环结束后, top<0||Stack[top]<h

                 if(h>)

                 {

                     Stack[++top]=h;    //    h入栈

                     len[top]=l+;    //    以top为起点的最长连续（h>=Stack[top])的区间长度

                 }

             }

 //            print();

         }

         printf("%lld\n",ans);

     }

 }