直方图中最大的矩形

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;

//l[i], r[i]表示第i个矩形的高度可向两侧扩展的左右边界
int h[N], q[N], l[N], r[N];

typedef long long LL;

int main()
{
    int n;
    while(scanf("%d", &n), n)
    {
        for(int i = 1; i <= n; i ++)  scanf("%d", &h[i]);
        h[0] = h[n + 1] = -1;

        int tt = -1;
        q[++ tt] = 0;
        for(int i = 1; i <= n; i ++)
        {
            while(h[q[tt]] >= h[i])  tt --;
            l[i] = i - q[tt];
            q[++ tt] = i;
        }

        tt = -1;
        q[++ tt] = n + 1;
        for(int i = n; i; i --)
        {
            while(h[q[tt]] >= h[i])  tt --;
            r[i] = q[tt] - i;
            q[++ tt] = i;
        }

        LL res = 0;
        for(int i = 1; i <= n; i ++)  res = max(res, (LL)h[i] * (l[i] + r[i] - 1));
        printf("%lld\n", res);
    }
    return 0;
}