POJ2559 Largest Rectangle in a Histogram

POJ

SPOJ

分析

毒瘤POJ，竟然不资瓷bits/stdc++.h。

用单调栈维护一下矩形就行了。

单调栈经典应用。

要开long long。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef int mainint;
#define int long long
using namespace std;

const int MAXN=100000+10;

int n,ans;
int a[MAXN],w[MAXN];
int sta[MAXN],top=0;

inline void solve() {
    for (re int i=1;i<=n;++i) scanf("%lld",a+i);
    ans=top=0; a[n+1]=0;
    for (re int i=1;i<=n+1;++i) {
        if (a[i]>sta[top]) sta[++top]=a[i],w[top]=1;
        else {
            int width=0;
            while (sta[top]>a[i]) {
                width+=w[top];
                ans=max(ans,width*sta[top]);
                --top;
            }
            sta[++top]=a[i],w[top]=width+1;
        }
    }
    printf("%lld\n",ans);
}

mainint main() {
    while (scanf("%lld",&n)) {
        if (!n) break;
        solve();
    }
    return 0;
}