AcWing 131. 直方图中最大的矩形
原题链接
简单
单调栈
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;
int n;
int h[N];
int stk[N], top; // 模拟栈
int l[N], r[N];
int main() {
while (scanf("%d", &n), n) {
for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
h[0] = h[n + 1] = -1;
top = 0;
stk[++top] = 0;
for (int i = 1; i <= n; i++) {
while (top && h[stk[top]] >= h[i]) top--;
l[i] = stk[top];
stk[++top] = i;
}
top = 0;
stk[++top] = n + 1;
for (int i = n; i >= 1; i--) {
while (top && h[stk[top]] >= h[i]) top--;
r[i] = stk[top];
stk[++top] = i;
}
ll res = 0;
for (int i = 1; i <= n; i++)
res = max(res, (ll)h[i] * (r[i] - l[i] - 1));
printf("%lld\n", res);
}
return 0;
}