题意:
给定$n$个矩形,第$i$个矩形的高度为:$h_i$,问这些矩形可以组成的最大矩形的面积。
数据范围:$1\leq n\leq 10^5$
题解:
暴力考虑本问题:
由每个矩形$x$向左右扩展至矩形的高度比$x$的高度低则停止,然后取$max$即可。
时间复杂度:$O(n^2)$
考虑如何优化本问题:
枚举每个矩形,以当前枚举到的第$i$个矩形为准,然后向左边扩展,当遇到一个矩形$j$,$h_j<h_i$,则矩形$j$左边的所有矩形高度都不会高于$h_j$,所以在枚举完以第$j$个矩形时,其左边的矩形高度都会被更新成不大于第$j$个矩形的高度。此时形成了一个单调递增的序列,同时每个序列会被记录数量。
所以枚举到第$i$个矩形时,先更新单调序列至序列中所有元素都单调递增但最大不超过$h_i$,所以在更新时矩形高度的同时也要更新答案,此时答案是第$j$个矩形可以向右扩展的最多矩形个数。
枚举完所有矩形后,再将已经得到的单调序列从栈顶开始分别再更新将高度减少至其单调序列的左边即可,更新时的操作同上。
时间复杂度:$O(n)$
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, x;
int stk[N], top;
int cnt[N];
ll res;
int main()
{
while(~scanf("%d", &n) && n > 0) {
top = 0;
res = 0;
for(int i = 1; i <= n; ++i) {
scanf("%d", &x);
res = max(res, (ll)x);
int act = 0;
while(top && stk[top] >= x) {
act += cnt[top];
res = max(res, 1ll * act * stk[top]);
--top;
}
stk[++top] = x;
cnt[top] = act + 1;
}
while(top >= 1) {
res = max(res, 1ll * cnt[top] * stk[top]);
cnt[top - 1] += cnt[top];
--top;
}
printf("%lld\n", res);
}
return 0;
}