题目描述

blablabla

算法1

(单调栈)

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 100010;
int h[N], r[N], l[N], q[N]; //q记录栈内元素的下标
int n, t;
long long res;
int main()
{
    while(scanf("%d", &n), n)
    {
        res = 0;
        t = 0;
        for(int i = 1; i <= n; i ++)
            cin >> h[i];
        h[0] = h[n + 1] = -1;  //初始化边界
        q[0] = 0;  //不能省，否则会挂
        for(int i = 1; i <= n; i ++)
        {
            while(h[i] <= h[q[t]]) t --;   //如果当前元素比栈顶大，就说明该元素左边第一个比它小的元素就是栈顶
                                        //反之，就一直删除栈顶，直到找到第一个比他小的数，然后该点入栈，取代所有比他大的数
            l[i] = q[t];
            q[++ t] = i;
        }
        t = 0;
        q[0] = n + 1; // 右边界
        for(int i = n; i; i --)
        {
            while(h[i] <= h[q[t]]) t --;
            r[i] = q[t];
            q[++ t] = i;
        }
        for(int i = 1; i <= n; i ++)
        {
            res = max(res, (long long)(r[i] - l[i] - 1) * h[i]); 
        }
        cout << res << endl;
    }
    return 0;
}