hdu 1506 히 스 토 그램 에서 가장 큰 사각형 (단조 로 운 스 택)

제목: n 개의 너비 가 1 높이 가 hi 인 장방형 을 드 립 니 다.
        동 그 라 미 를 칠 수 있 는 최대 장방형 의 면적 이 얼마나 되 는 지 물 어보 세 요.
생각:http://blog.csdn.net/dgq8211/article/details/7740610

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<stack>

using namespace std;

#define ll __int64

struct Node

{

    int wid;

    ll hi;

    ll s;

};

Node node[100000+1000];

int main()

{

    int n,h;

    int i,j,k;

    int l,r;

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

    {

        stack<Node> q;

        ll maxx=0;

        Node now;

        now.hi=-1;

        now.wid=0;

        q.push(now);

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

        {

          //printf("%d
",i);

          if(i!=n) scanf("%d",&h);

          else h=0;

          if(h>q.top().hi)

          {

            now.hi=h;

            now.wid=1;

            q.push(now);

          }

          else

          {

            int cnt=0;

            while(q.top().hi>=h)

            {

              now=q.top();

              q.pop();

              maxx=max(maxx,(cnt+now.wid)*now.hi);

              cnt+=now.wid;

            }

            now.wid=cnt+1;

            now.hi=h;

            q.push(now);

          }

        }



        printf("%I64d
",maxx);

    }

    return 0;

}