题目描述
直方图是由在公共基线处对齐的一系列矩形组成的多边形。
矩形具有相等的宽度,但可以具有不同的高度。
例如,图例左侧显示了由高度为2,1,4,5,1,3,3的矩形组成的直方图,矩形的宽度都为1:
通常,直方图用于表示离散分布,例如,文本中字符的频率。
现在,请你计算在公共基线处对齐的直方图中最大矩形的面积。
图例右图显示了所描绘直方图的最大对齐矩形。
输入格式
输入包含多个测试用例
每行先输入一个 $n$ 表示组成直方图的矩形个数,后面跟 $n$ 个整数表示每个矩形的高度
当 $n$ 为 $0$ 时结束。
习自@yxc 大佬的视频课
首先考虑暴力做法,以每个矩形的高度为准,向两边扩展,直到遇到比它矮的为止
如图所示,记录每个矩形向两侧扩展的边界 $[l, r]$
它扩展出的矩形面积为 $ s = (r - l + 1) * h $
最优解会在这些扩展出的矩形中产生。
-
时间复杂度 $O(n^2)$
每个矩形向两侧扩展的最大宽度为矩形个数 $n$,共进行 $n$ 次这样的操作
单调栈优化
在计算每个矩形可以扩展的左边界时,可以发现有一些矩形是可以不考虑的
如图所示,由于2号矩形的存在,在计算2右边的矩形的左边界时,可以不考虑1号矩形。
高度高于2号的矩形会被2卡住,高度小于等于2号的也必然小于等于1号。
观察可知,在计算左边界时,靠左的且较高的矩形可以省略,因此可以用单调栈优化。
q[tt]
作为栈顶元素下标,当满足h[q[tt]] >= h[i]
时,弹出栈顶
时间复杂度 $O(n)$
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
//l[i], r[i]表示第i个矩形的高度可向两侧扩展的左右边界
int h[N], q[N], l[N], r[N];
typedef long long LL;
int main()
{
int n;
while(scanf("%d", &n), n)
{
for(int i = 1; i <= n; i ++) scanf("%d", &h[i]);
h[0] = h[n + 1] = -1;
int tt = -1;
q[++ tt] = 0;
for(int i = 1; i <= n; i ++)
{
while(h[q[tt]] >= h[i]) tt --;
l[i] = i - q[tt];
q[++ tt] = i;
}
tt = -1;
q[++ tt] = n + 1;
for(int i = n; i; i --)
{
while(h[q[tt]] >= h[i]) tt --;
r[i] = q[tt] - i;
q[++ tt] = i;
}
LL res = 0;
for(int i = 1; i <= n; i ++) res = max(res, (LL)h[i] * (l[i] + r[i] - 1));
printf("%lld\n", res);
}
return 0;
}
-
每个矩形的高度都是>=0的,为了使得每个矩形的两侧都有矮于它的矩形,
所以往两侧放了两个-1的矩形
h[0] = h[n + 1] = -1;
-
由于有-1矩形的存在,不会有任何矩形的高度 $h$ 满足 $-1 >= h$,所以栈不会空
因此可以省略栈中是否有元素的判断条件
tt >= 0
贴个双端队列的~
为啥在判断右边时for循环中第二个参数是i,而不是i>=1
一样的,0就是false了。能保证 i 从大往小不会跳过0就可以这么写
%%%
哇,跟笛卡尔树解法有异曲同工之妙
太感谢了啊
女少口阿
代码中有双层循环,仅仅外层就要遍历n次,为啥时间复杂度是O(n)
每一个点被遍历了一次,所以时间复杂度$O(n)$
外层的遍历是常数的,题目中说的是
输入包含几个测试用例
,只有常数个因为踢馆的时候每个条入栈一次,最多被踢一次,所以是O(n),能明白吗
问个问题,(LL)h[i] * (l[i] + r[i] - 1)如果改成(LL)(h[i] * (l[i] + r[i] - 1))就会WA,不太明白
先int * int就爆了,要先转成ll
懂了懂了,谢谢
往一个方向扩展行不?
不行,图上橙色的那个矩形会考虑不到
多谢大神
实际上是可以的
实际上只需要在出栈的时候更新R[]就行了 不需要第二次求R[] hhh滑稽爷的题解太猛啦
为啥栈一开始要q[++tt]=0?
这个可以看我代码后面,往两侧放了高度为-1的边界,这个是先把边界放进栈里
哦哦,这样写边界就不用特判了对吧
是的
最后为什么不是r[i] - l[i] + 1啊?
啊因为
l,r
数组存的并不是下标,而是包含i
的向左或右延伸的最大长度感谢感谢 了解了~
跟上大佬的步伐
枫
666大佬写的很清楚啊