单调栈

BF

这个题一个比较直接的想法是，选定一个高度h，然后向左右扩展，直到遇到边界，即高度小于选定高度h，然后枚举h，对每一次枚举的结果去一个最大值，就是答案

优化

但是由于需要枚举h，再加上向左右扩展，导致时间复杂度是n^2级别的，显然会超时
然后考虑怎么去优化

先只考虑左侧边界

对于每一个高度h，（假设左侧边界l）我们显然只在乎它左侧第一个小于h元素的位置，枚举的下一个高度h1如果小于h，那么在 l ~ h_pos 范围内都是可取的，只需要在l左侧寻找边界，如果h1大于h，边界显然是h_pos，
所以 l ~ h_pos 显然就没用了，也就是可删的
这样频繁在序列后侧进行增删操作，显然需要使用栈结构，并且是单调的

对于右边界

我们将整个序列逆序遍历即可

代码

while(!s.empty() && a[s.top()] >= a[i]) s.pop();
当前元素如果和栈顶元素相同，那么栈顶元素显然是可取的，而我们使用栈的目的是寻找边界，所以出栈
res = max(res, (LL)(r[i] - l[i] - 1) * a[i]);
l和r数组分别保存两侧边界，并且边界不可取，也就是求[l + 1, r - 1]的长度,长度为r[i] - l[i] - 1

边界情况

左侧
如果说，h比前面的所有元素都要小，栈就一定会清空，此时可以令l[i] = -1，因为l，r两个数组保存的是不可取边界
右侧
同理，取n

#include <iostream>
#include <stack>

using namespace std;

typedef long long LL;
const int N = 100005;
LL a[N];
int n;

int l[N], r[N];  

int main()
{
    while(cin >> n, n)
    {
        for(int i = 0; i < n; i++) cin >> a[i];

        stack<int>s;
        for(int i = 0; i < n; i++)
        {

            while(!s.empty() && a[s.top()] >= a[i]) s.pop();
            l[i] = (s.empty() ? -1 : s.top());
            s.push(i);
        }

        // s.clear();
        s = stack<int>();   //将栈清空

        for(int i = n - 1; i >= 0; i--)
        {

            while(!s.empty() && a[s.top()] >= a[i]) s.pop();
            r[i] = (s.empty() ? n : s.top());
            s.push(i);
        }

        LL res = 0;
        for(int i = 0; i < n; i++)
        {
            res = max(res, (LL)(r[i] - l[i] - 1) * a[i]);
        }

        cout << res << endl;
    }
    return 0;
}