单调栈

时间复杂度

$O(n)$

C++ 代码

#include<iostream>
#include<stack>
using namespace std;
const int N = 1e5 + 7;
typedef long long ll;
ll h[N],l[N];
int main()
{
    int n;
    h[0] = -1;
    while(cin>>n&&n)
    {
        for (int i = 1; i <= n;i++)
            cin >> h[i];
        h[n + 1] = -1;
        stack<int> sk;
        sk.push(0);
        for (int i = 1; i <= n;i++)
        {
            while(h[sk.top()]>=h[i])
            {
                sk.pop();
            }
            l[i] = sk.top();
            sk.push(i);
        }
        while(sk.size())
            sk.pop();
        sk.push(n + 1);
        ll res = 0;
        for (int i = n; i >= 1;i--)
        {
            // cout << 1;
            while(h[sk.top()]>=h[i])
            {
                sk.pop();
            }
            int r = sk.top();
            res = max(res, (r - l[i] - 1) * h[i]);
            sk.push(i);
        }
        cout << res << endl;
    }
}