最近新见识到了几道题,大概或许可能对单调栈有了点新的理解吧。
题源:戳我
题意: 给定$n$个的矩形,第$i$个矩形的长度为$h_i$,这些矩形按照给定的顺序拼接起来,可以得到的最大的矩形面积是多少。
$1\leq n\leq 10^5$
题解:
先考虑最暴力的做法:枚举选定的矩形长度,然后找到选定区间内的最低高度,更新答案。
时间复杂度:$O(n^3)$
考虑优化:枚举矩形$i$的高度$h_i$作为其所在区间的最低高度,那么向两边扩展至将要扩展的矩形$j$的高度$h_j<h_i$时停止,用扩展后的区间来更新答案。
时间复杂度:$O(n^2)$
由于该时间复杂度仍然不满足题目的要求,所以考虑进一步优化。
枚举矩形$i$的高度$h_i$为当前枚举过的矩形中的最高高度,因此需要在枚举前先更新已经有的序列的高度,这样就维护了一个单调递增的序列,由于每次都是将枚举的$i$的高度$h_i$作为该序列的最高高度加入到序列中,$h_i$加入前需要先对已有元素进行更新的操作,满足单调栈的性质。具体的操作是:在对已有元素进行更新时,必然是把其高度削减为$h_i$,那么此时可能削减前的高度乘上数量是最终答案,所以需要在此时更新下答案,然后再削减高度更新数量。
在单调栈建立完毕后,仍然有一些高度未被作为矩形的高度去更新答案,因此再从栈顶依次将这些元素作为矩形高度去更新答案即可。
时间复杂度:$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;
}
练习:$Leetcode\ 84, Leetcode\ 85, Acwing\ 152$