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

╰+哭是因爲堅強的太久メ 2021-12-20 04:51 153阅读 0赞

[题目描述 ][Link 1]

柱状图是有一些宽度相等的矩形下端对齐以后横向排列的图形，但是小A的柱状图却不是一个规范的柱状图， **它的每个矩形下端的宽度可以是不相同的一些整数**，分别为 a\[i\]

每个矩形的高度是h\[i\]

,现在小A只想知道，在这个图形里面包含的最大矩形面积是多少。

![311278_1552569026989_4FD14CED91FC0F06AE67FE9FE012D46C][]

## 输入描述: ##

一行一个整数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 + 10;
    const ull seed = 131;
    const int INF = 0x3f3f3f3f;
    const int MOD = 1000000007;
    struct node{
        ll hei;
        int pos;
        node(int p = 0, ll h = 0): pos(p), hei(h){}
    }s[maxn];
    ll sum[maxn], h[maxn];
    int n, top;
    ll solve(){
        ll ans = 0;
        top = 0;
        for(int i = 1; i <= n; i++){
            if(top == 0 || h[i] >= s[top].hei) s[++top] = node(i, h[i]);
            else{
                int r, l;
                while(top > 0 && s[top].hei > h[i]){
                    r = i - 1;
                    l = (top == 1? 0 : s[top - 1].pos);
                    ans = max(ans, s[top].hei * (sum[r] - sum[l]));
                    --top;
                }
                s[++top] = node(i, h[i]);
            }
        }
        if(top > 0){
            int r, l;
            r = s[top].pos;
            while(top > 0){
                l = (top == 1? 0 : s[top - 1].pos);
                ans = max(ans, s[top].hei * (sum[r] - sum[l]));
                --top;
            }
        }
        return ans;
    }
    int main(){
        scanf("%d", &n);
        sum[0] = 0;
        for(int i = 1; i <= n; i++){
            scanf("%lld", &sum[i]);
            sum[i] += sum[i - 1];
        }
        for(int i = 1; i <= n; i++)
            scanf("%lld", &h[i]);
        printf("%lld\n", solve());
        return 0;
    }

转载于:https://www.cnblogs.com/KirinSB/p/10701487.html

[Link 1]: https://ac.nowcoder.com/acm/contest/549/H
[311278_1552569026989_4FD14CED91FC0F06AE67FE9FE012D46C]: /images/20211220/a598a64634924ccd8e083087bf424460.png