newcoder 小A的柱状图（单调栈）题解

时间：2021-10-12 20:52:25

题目描述

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

输入描述:

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

输出描述:

一行一个整数，表示最大的矩形面积
 
思路：
先用前缀和维护宽度。我们把宽度为a[i]想成a[i]个宽度为1的放在一起就行了。我们如果能找到某一高度的左右第一个比他小的位置，那么就能求出以他为高的最大值。显然直接暴力n方复杂度。那么我们这里可以用单调栈维护一下。我们每次对比栈顶和入栈高度hi，如果栈顶小与等于hi，那么hi入栈，因为显然此时我没找到栈顶最右第一个比它小的，直到hi比栈顶小，那么我栈顶右一就是当前的i，左一就是S[top-1]。
代码：
#include<cmath>

#include<set>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include <iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn = 1e6 + ;

const ull seed = ;

const int INF = 0x3f3f3f3f;

const int MOD = ;

struct node{

    ll hei;

    int pos;

    node(int p = , ll h = ): pos(p), hei(h){}

}s[maxn];

ll sum[maxn], h[maxn];

int n, top;

ll solve(){

    ll ans = ;

    top = ;

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

        if(top ==  || h[i] >= s[top].hei) s[++top] = node(i, h[i]);

        else{

            int r, l;

            while(top >  && s[top].hei > h[i]){

                r = i - ;

                l = (top == ?  : s[top - ].pos);

                ans = max(ans, s[top].hei * (sum[r] - sum[l]));

                --top;

            }

            s[++top] = node(i, h[i]);

        }

    }

    if(top > ){

        int r, l;

        r = s[top].pos;

        while(top > ){

            l = (top == ?  : s[top - ].pos);

            ans = max(ans, s[top].hei * (sum[r] - sum[l]));

            --top;

        }

    }

    return ans;

}

int main(){

    scanf("%d", &n);

    sum[] = ;

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

        scanf("%lld", &sum[i]);

        sum[i] += sum[i - ];

    }

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

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

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

    return ;

}

相关文章