牛客小白月赛13 小A的柱状图（单调栈）

时间：2024-05-23 18:35:50

链接：https://ac.nowcoder.com/acm/contest/549/H
来源：牛客网

题目描述

柱状图是有一些宽度相等的矩形下端对齐以后横向排列的图形，但是小A的柱状图却不是一个规范的柱状图，它的每个矩形下端的宽度可以是不相同的一些整数，分别为a[i]a[i],每个矩形的高度是h[i]h[i],现在小A只想知道，在这个图形里面包含的最大矩形面积是多少。
牛客小白月赛13 小A的柱状图（单调栈）

输入描述:

一行一个整数N，表示长方形的个数
接下来一行N个整数表示每个长方形的宽度
接下来一行N个整数表示每个长方形的高度

输出描述:

一行一个整数，表示最大的矩形面积
示例1

输入

复制

7

1 1 1 1 1 1 1

2 1 4 5 1 3 3

输出

复制

8

说明

样例如图所示，包含的最大矩形面积是8

备注:

1≤n≤1e6,1≤a[i]≤100,1≤h[i]≤1e9

解题思路：很明显是单调栈的模板题，找到某长方形最左边和最右边比它高度低的位置，然后求他们的总宽度，就可以求出总面积了。
单调栈简单实现过程：先找到最左边的位置l【i】，取某长方形的高度，将其与栈顶的长方形作比较，如果比栈顶的长方形高，那么l【i】=sta.top()(sta为栈)；如果比它低，那么栈顶元素出栈，继续比较，如果栈空了，那么l【i】=0；
同理可求得最右边的位置r【i】。
#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+5;

typedef long long ll;

int w[maxn];

int h[maxn];

ll sumw[maxn];

stack<int> sta;

int l[maxn],r[maxn];

int main(){

    int n;

    scanf("%d",&n);

    sumw[0]=0;

    for(int i=1;i<=n;i++){

        scanf("%d",&w[i]);

        sumw[i]=sumw[i-1]+1ll*w[i];

    }

    for(int i=1;i<=n;i++){

        scanf("%d",&h[i]);

    }

    for(int i=1;i<=n;i++){

        while(!sta.empty()&&h[i]<=h[sta.top()]) sta.pop();

        if(!sta.empty())l[i]=sta.top();

        else l[i]=0;

        sta.push(i);

    }

    while(!sta.empty())sta.pop();

    for(int i=n;i>=1;i--){

        while(!sta.empty()&&h[i]<=h[sta.top()])sta.pop();

        if(!sta.empty())r[i]=sta.top()-1;

        else r[i]=n;

        sta.push(i);

    }

    ll ans=0;

    for(int i=1;i<=n;i++){

        ll tem=(sumw[r[i]]-sumw[l[i]])*h[i];

        ans=max(ans,tem);

    }

    printf("%lld\n",ans);

    return 0;

}

　　

相关文章