解题思路

单调栈的基础应用。我们以矩形高度为单位建立一个单调不降的栈，每次输入一个新的矩形高度 h 时，如果新的高度比栈顶高度低，则一直 pop，并累计 pop 出的元素的宽度，每次 pop 我们都可以看做得到一个高度为 h，宽度为累计总宽度的一个矩形（可以看做是把这段的所有矩形高度都削减为 h），用它的面积更新答案。pop 结束后将我们最终得到的新矩形入栈即可。

参考代码

#include <cstdio>
#include <stack>
using namespace std;

struct info {
    int h, w;
};

int main(int argc, char const *argv[]) {
    int n, h;
    while(scanf("%d", &n), n) {
        stack<info> s;
        long long ans = 0;
        for(int i=0; i<n; ++i) {
            scanf("%d", &h);
            int w = 0;
            while(!s.empty() && s.top().h>h) {
                w += s.top().w;
                ans = max(ans, 1LL*s.top().h*w);
                s.pop();
            }
            s.push((info){h, w+1});
        }
        int w = 0;
        while(!s.empty() ) {
            w += s.top().w;
            ans = max(ans, 1LL*s.top().h*w);
            s.pop();
        }
        printf("%lld\n", ans);
    }
    
    return 0;
}