之前写个一道差不多的题：Largest Rectangle in a Histogram（单调栈）
题目大意 / Problem
柱状图是有一些宽度相等的矩形下端对齐以后横向排列的图形，但是小A的柱状图却不是一个规范的柱状图，它的每个矩形下端的宽度可以是不相同的一些整数，分别为a[i]a[i]a[i],每个矩形的高度是h[i]h[i]h[i],现在小A只想知道，在这个图形里面包含的最大矩形面积是多少。
思路 / Thought
用单调栈来维护一个点往左和向右分别可以延长多少。
构造一个单调不减栈，以从左往右为例。也就是当h[i]大于栈内最大高度时直接加入到栈中，说明左边不存在比h[i]更高的柱形，也就是说向左延伸距离为0。
只要栈顶存在且高度大于等于h[i]说明从i这个点可以向左延伸，就将栈顶单位的宽度加入到l[i]中。
最后将l[i] + 1存入栈中，因为l[i] + 1个单位都被合并到i这个单位中了，以便于加到后面的单位中。
计算r[i]只需要改变方向即可，不要忘记清空栈。
代码 / Code
//Copyright (C) Eriktse 2022
#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
//64bit IO Format: %lld
using namespace std;
const int maxn = 1e6 + 9;
int a[maxn], b[maxn], prefix[maxn];
int l[maxn], r[maxn];//分别表示左右最大宽度
pair<int, int> stk[maxn];//{宽度，高度}
int top = 0;//构造单调递增栈
signed main()
{
int N;scanf("%lld", &N);
for(int i = 1;i <= N; ++ i)scanf("%lld", a + i);
for(int i = 1;i <= N; ++ i)scanf("%lld", b + i);
for(int i = 1;i <= N; ++ i)prefix[i] = prefix[i - 1] + a[i];
for(int i = 1;i <= N; ++ i)
{
while(top && b[i] <= stk[top].se)l[i] += stk[top --].fi;
stk[++ top] = {l[i] + 1, b[i]};
}
top = 0;
for(int i = N;i >= 1; -- i)
{
while(top && b[i] <= stk[top].se)r[i] += stk[top --].fi;
stk[++ top] = {r[i] + 1, b[i]};
}
int ans = 0;
for(int i = 1;i <= N; ++ i)
{
int tmp = (prefix[i + r[i]] - prefix[i - l[i] - 1]) * b[i];
ans = max(ans, tmp);
}
printf("%lld\n" ,ans);
return 0;
}
文章评论