#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n, h[N], stk[N];
int l[N], r[N]; // 对于高度h[i],l[i]存储其左边第一个比其矮的h的下标,r[i]同理;一个下标对应一整个矩形,而不是其左/右边长
void get_bound(int bound[N]) {
int tt = 0;
h[0] = -1; // 哨兵,若左/右边没有比其矮的h,则l/r就存储0
for (int i = 1; i <= n; i ++) {
while (h[stk[tt]] >= h[i]) tt --; // 单调栈
bound[i] = stk[tt]; // 存储的是下标
stk[++ tt] = i;
}
}
int main() {
while (cin >> n, n) {
for (int i = 1; i <= n; i ++) cin >> h[i];
get_bound(l);
reverse(h + 1, h + 1 + n); // 翻转h,这样就可以用get求右边的情况
get_bound(r);
reverse(h + 1, h + 1 + n); // 再翻转回来
reverse(r + 1, r + 1 + n); // r中存储的下标 针对的是翻转后的h
long long res = 0;
for (int i = 1; i <= n; i ++)
res = max(res, h[i] * ((n + 1 - r[i]) - l[i] - (long long)1));
cout << res << endl;
}
return 0;
}
原理
对于每一个矩形的顶边,分别向两边扩展,直到遇到第一个比该矩形更矮的矩形为止;求出由该顶边、底边和左右边围成的矩形面积。题目给出几个矩形,就需要求解几次,最后取面积的最大值。