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

题目链接

对栈的一种灵活运用吧算是，希望我的注释写的足够清晰。。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=100010;
int Stack[N];    //Stack[]为单调栈（即每次能入栈的元素值必比栈顶元素（若存在）要大） 
int len[N];        //len[]与Stack[]同步 ，记录的是从Stack[]中对应元素起向左最大可延伸的宽度 
int n;
LL top,ans,h;

void print()
{
    printf("top=%d,    ans=%d
",top,ans);
    printf("	Stack:");
    for(int i=0;i<=top;i++)
        printf("%6d",Stack[i]);
    puts("");
    printf("	  len:");
    for(int i=0;i<=top;i++)
        printf("%6d",len[i]);
    puts("");
}

int main()
{
    while(scanf("%d",&n)&&n)
    {
        memset(Stack,0,sizeof(Stack));
        memset(len,0,sizeof(len)); 
        top=-1,ans=0;
        for(int i=0; i<=n; i++)
        {
            if(i<n) scanf("%lld",&h);
            else h=-1;    //用作结束标记 
            if(top<0||Stack[top]<h)
            {
                Stack[++top]=h;    //    h入栈
                len[top]=1;        //    显然新入栈元素比原栈顶元素大，此时向左最大延伸“1”宽度 
            }                    //  “1”可根据具体题目进行修改~ 
            else    // if(top>=0&&Stack[top]>=h
            {
                int l=0;
                while(Stack[top]>=h&&top>=0)
                {
                    ans=max(ans,(LL)(len[top]+l)*Stack[top]);    //更新ans 
                    l+=len[top--];    //Stack[]和len[]同时将栈顶元素弹出 
                }    //循环结束后, top<0||Stack[top]<h 
                if(h>0)
                {
                    Stack[++top]=h;    //    h入栈 
                    len[top]=l+1;    //    以top为起点的最长连续（h>=Stack[top])的区间长度 
                }
            }
//            print();
        }
        printf("%lld
",ans);
    }
}