poj-2359 Larget Rectanglen a Higogram(単調スタック)

poj 2559
問題を解く
各矩形に対して、左右にスキャンして、最初の高さより小さい長方形を見つけます.
単調なインクリメントスタックを維持する、すなわちスタックの底からスタックの一番上まで厳格にインクリメントする、そうすると、スタックの一番目はより小さい値です.2つの配列を維持し、L[i]とR[i]はそれぞれi番目の矩形の2つの下付きを表す.

#include 
#include 
#include 
using namespace std;

typedef long long ll;
const int maxn = 100000 + 10;
int   n;
int   h[maxn];
int   L[maxn], R[maxn], stack[maxn];

void solve()
{
    int k = 0;
    for(int i = 0; i < n; ++i){
        while(k > 0 && h[stack[k - 1]] >= h[i]) --k;
        L[i] = (k == 0 ? 0 : stack[k - 1] + 1);
        stack[k++] = i;
    }

    k = 0;
    for(int i = n - 1; i >= 0; --i){
        while(k > 0 && h[stack[k - 1]] >= h[i]) --k;
        R[i] = (k == 0 ? n : stack[k - 1]);
        stack[k++] = i;
    }

    ll ans = 0;
    for(int i = 0; i < n; ++i){
        //printf("L:%d   R:%d   T:%d
", L[i], R[i], h[i] * (R[i] - L[i]));
        ans = max(ans, (ll)h[i] * (R[i] - L[i]));
    }
    printf("%I64d
", ans);
}


int main()
{
#ifdef LOCAL
freopen("data.in", "r", stdin);
#endif
    while(cin >> n && n){
        for(int i = 0; i < n; ++i) scanf("%d", h + i);
            solve();
    }

    return 0;
}