题目
题 目 传 送 门 题目传送门 题目传送门
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAzNfRHLGZkRGZkRfJ3bs92YsYTMfVmepNHL3FFRPp3aE5EMNpHW4Z0MMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnL5YTOwMjNxgTM4IjNwkTMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
题解
- 如果矩形的高度从左向右单调递增,那么我们可以枚举每个矩形的高度,并把宽度延伸到左右边界,来计算面积,从中取得最大值来得到答案。
- 但实际上矩形高度不可能是单调递增的。
- 那么我们可以维护一个高度递增且宽度递增的矩形序列。
-
具体过程:
我们可以建一个栈用来保存每个矩形的高度。
从左向右遍历每个矩形,如果高度比栈顶高直接进栈。
如果高度小于栈顶,则不断取出栈顶,直到栈顶高度比当前高度小,在出栈的过程中我们累加出栈矩形的宽度,每弹出一个矩形就用高度乘以宽度来记录该矩形的面积,在整个过程结束后我们把一个宽度为当前累加的宽度,高度为当前宽度的矩形进栈。
code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 1000;
typedef long long LL;
template <typename T>
inline void read(T &s) {
s = 0;
T w = 1, ch = getchar();
while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
s *= w;
}
int n, cnt;
LL ans;
LL a[maxn], s[maxn], w[maxn];
int main() {
while (scanf("%d", &n) && n != 0) {
a[n + 1] = 0;
cnt = 0;
ans = 0;
memset(s, 0, sizeof(s));
memset(w, 0, sizeof(w));
for (int i = 1; i <= n; ++i) read(a[i]);
for (int i = 1; i <= n + 1; ++i) {
if (a[i] > s[cnt]) {
s[++cnt] = a[i];
w[cnt] = 1;
} else {
int width = 0;
while (s[cnt] > a[i]) {
width += w[cnt];
ans = max(ans, (LL) width * s[cnt]);
cnt--;
}
s[++cnt] = a[i];
w[cnt] = width + 1;
}
}
printf("%lld\n", ans);
}
return 0;
}