AcWing 131. 直方图中最大的矩形【单调栈】

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 131. 直方图中最大的矩形【单调栈】原题链接简单

作者：

滑稽_ωﾉ , 2019-10-26 11:22:00 , 所有人可见 , 阅读 9259

90

18

题目描述

直方图是由在公共基线处对齐的一系列矩形组成的多边形。

矩形具有相等的宽度，但可以具有不同的高度。

例如，图例左侧显示了由高度为2,1,4,5,1,3,3的矩形组成的直方图，矩形的宽度都为1：

通常，直方图用于表示离散分布，例如，文本中字符的频率。

现在，请你计算在公共基线处对齐的直方图中最大矩形的面积。

图例右图显示了所描绘直方图的最大对齐矩形。

输入格式

输入包含多个测试用例

每行先输入一个 $n$ 表示组成直方图的矩形个数，后面跟 $n$ 个整数表示每个矩形的高度

当 $n$ 为 $0$ 时结束。

习自@yxc 大佬的视频课

首先考虑暴力做法，以每个矩形的高度为准，向两边扩展，直到遇到比它矮的为止

QQ图片20191026001320.png

如图所示，记录每个矩形向两侧扩展的边界 $[l, r]$

它扩展出的矩形面积为 $ s = (r - l + 1) * h $

最优解会在这些扩展出的矩形中产生。

时间复杂度 $O(n^2)$

每个矩形向两侧扩展的最大宽度为矩形个数 $n$，共进行 $n$ 次这样的操作

单调栈优化

在计算每个矩形可以扩展的左边界时，可以发现有一些矩形是可以不考虑的

QQ图片20191026004515.png

如图所示，由于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

28 评论

G1842043669 2024-03-24 11:49

#include<iostream>  // 引入输入输出流库
#include<deque>     // 引入双端队列库

using namespace std;  // 使用标准命名空间

const int N = 100010;  // 定义常量N，表示直方图的最大矩形数

// l[i], r[i]表示第i个矩形的高度可向两侧扩展的左右边界
int h[N], l[N], r[N];  // 定义三个数组，分别存储矩形的高度、左边界和右边界

typedef long long LL;  // 定义长整型别名LL

int main()  // 主函数
{
    int n;  // 定义变量n，表示直方图的矩形数
    while(scanf("%d", &n), n)  // 读取输入的矩形数，当n不为0时继续执行循环
    {
        for(int i = 1; i <= n; i ++)  scanf("%d", &h[i]);  // 读取每个矩形的高度
        h[0] = h[n + 1] = -1;  // 设置两个哨兵元素的高度为-1

        deque<int> q;  // 创建一个双端队列q
        q.push_back(0);  // 将0压入队列q的末尾
        for(int i = 1; i <= n; i ++)  // 遍历每个矩形
        {
            while(!q.empty() && h[q.back()] >= h[i])  q.pop_back();  // 当队列非空且队尾元素大于等于当前矩形高度时，弹出队尾元素
            l[i] = i - q.back();  // 计算当前矩形的左边界
            q.push_back(i);  // 将当前矩形的索引压入队列q的末尾
        }

        while(!q.empty())  q.pop_back();  // 清空队列q
        q.push_back(n + 1);  // 将n+1压入队列q的末尾
        for(int i = n; i; i --)  // 逆序遍历每个矩形
        {
            while(!q.empty() && h[q.back()] >= h[i])  q.pop_back();  // 当队列非空且队尾元素大于等于当前矩形高度时，弹出队尾元素
            r[i] = q.back() - i;  // 计算当前矩形的右边界
            q.push_back(i);  // 将当前矩形的索引压入队列q的末尾
        }

        LL res = 0;  // 定义长整型变量res，用于存储最大矩形的面积
        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，表示程序正常结束
}

G1842043669 2024-03-24 11:50

贴个双端队列的~

ζ凉心º 2022-10-22 09:23

为啥在判断右边时for循环中第二个参数是i，而不是i>=1

滑稽_ωﾉ 2022-10-24 21:36

一样的，0就是false了。能保证 i 从大往小不会跳过0就可以这么写

t123456789009 2023-12-15 15:53

%%%

秋似火 2023-06-03 08:50

太感谢了啊

xiyu03 2022-10-12 22:57

女少口阿

jieqiang 2022-07-16 18:48

代码中有双层循环，仅仅外层就要遍历n次，为啥时间复杂度是O（n）

incra 2022-07-22 16:27

每一个点被遍历了一次，所以时间复杂度$O(n)$

Anohkx 2023-10-18 19:03

外层的遍历是常数的，题目中说的是输入包含几个测试用例，只有常数个

孤独与我 2022-02-19 14:55

问个问题，(LL)h[i] * (l[i] + r[i] - 1)如果改成(LL)(h[i] * (l[i] + r[i] - 1))就会WA，不太明白

滑稽_ωﾉ 2022-02-19 15:54

先int * int就爆了，要先转成ll

孤独与我 2022-02-19 22:34 回复了滑稽_ωﾉ的评论

懂了懂了，谢谢

253718226 2021-09-08 08:44

往一个方向扩展行不？

滑稽_ωﾉ 2021-09-08 10:56

不行，图上橙色的那个矩形会考虑不到

253718226 2021-09-08 14:59 回复了滑稽_ωﾉ的评论

多谢大神

the_xin 2021-10-20 20:13 回复了滑稽_ωﾉ的评论

实际上是可以的

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e6+10;
int L[N],R[N],stk[N],top;
int a[N];
int main(){
    int n;
    while(scanf("%d",&n)){
        if(!n)break;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        stk[top=1]=1;
        L[1]=0;
        for(int i=2;i<=n;i++){
            while(top&&a[stk[top]]>a[i])R[stk[top--]]=i;
            L[i]=stk[top];
            stk[++top]=i;
        }
        while(top)R[stk[top--]]=n+1;
        long long ans=0;
        for(int i=1;i<=n;i++){
            //cout<<i<<" "<<a[i]<<" "<<R[i]-L[i]<<endl;
            ans=max(ans,1ll*(R[i]-L[i]-1)*a[i]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}