链接:https://ac.nowcoder.com/acm/contest/549/H
来源:牛客网
柱状图是有一些宽度相等的矩形下端对齐以后横向排列的图形,但是小A的柱状图却不是一个规范的柱状图,它的每个矩形下端的宽度可以是不相同的一些整数,分别为a[i]每个矩形的高度是h[i],现在小A只想知道,在这个图形里面包含的最大矩形面积是多少。
单调栈的模板题,考虑每个位置向两边拓展的最左边的边界和最右边的边界
L[i],R[i],分别从左到有和从右到左用一个单调栈维护。处理一下底边的前缀和,扫一遍就可以求出最大值。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 5;
ll a[maxn + 5], b[maxn + 5];
ll sum[maxn + 5];
ll Max(ll a, ll b) {
return a > b ? a : b;
}
int main() {
ll n;
scanf("%lld", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &b[i]);
}
for(int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
ll ans = 0;
stack<ll> s1, s2;
s1.push(-1);
s2.push(0);
a[n + 1] = -1;
for(int i = 1; i <= n + 1; i++) {
ll with = 0;
while(s1.top() > a[i]) {
ll x = s1.top();
with += s2.top();
ans = Max(ans, 1LL * with * x);
s1.pop(); s2.pop();
}
s1.push(a[i]);
s2.push(with + b[i]);
}
printf("%lld\n", ans);
return 0;
}
版本二:
以当前为最小值,维护左右边界
然后再遍历一遍
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 5;
ll a[maxn];
ll L[maxn], R[maxn];
ll sum[maxn];
stack<int> s;
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &sum[i]);
sum[i] += sum[i - 1];
}
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
a[n + 1] = -1e18;
a[0] = -1e18;
for (int i = 1; i <= n + 1; i++) {
ll sum = 0;
while (!s.empty() && a[s.top()] > a[i]) {
L[s.top()] = i - 1;
s.pop();
}
s.push(i);
}
while(!s.empty()) {
s.pop();
}
for (int i = n; i >= 0; i--) {
while (!s.empty() && a[s.top()] > a[i]) {
R[s.top()] = i + 1;
s.pop();
}
s.push(i);
}
ll ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, 1LL * (sum[L[i]] - sum[R[i] - 1]) * a[i]);
}
printf("%lld\n", ans);
return 0;
}