【POJ 2559】 Largest Rectangle in a Histogram

【题目链接】
【算法】
单调栈
【代码】
#include <algorithm>

#include <bitset>

#include <cctype>

#include <cerrno>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <limits>

#include <list>

#include <map>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <utility>

#include <vector>

#include <cwchar>

#include <cwctype>

#include <stack>

#include <limits.h>

using namespace std;

#define MAXN 100010

int i,top,n;

long long a[MAXN],s[MAXN],w[MAXN],stk[MAXN];

long long ans,tmp;

int main()

{

        while (scanf("%d",&n) != EOF && n)

        {

                for (i = ; i <= n; i++) scanf("%lld",&a[i]);

                ans = -;

                a[++n] = -;

                s[top = ] = -;

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

                {

                        if (a[i] >= s[top])

                        {

                                s[++top] = a[i];

                                w[top] = ;

                        } else

                        {

                                tmp = ;

                                while (a[i] < s[top])

                                {

                                        tmp += w[top];

                                        ans = max(ans,tmp*s[top]);

                                        top--;

                                }

                                s[++top] = a[i]; w[top] = tmp + ;

                        }

                }

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

        }

        return ;

}