[单调栈]小A的柱状图

链接：https://ac.nowcoder.com/acm/problem/23619
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

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

输入描述:

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

输出描述:

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

示例1

输入

复制

7

1 1 1 1 1 1 1

2 1 4 5 1 3 3

输出

复制

说明

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

备注:

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

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int amn=1e6+;

 ll a[amn],h[amn],s[amn];

 int main(){

     ll n,tp,d,ans,idx;

     while(cin>>n){

         a[]=;

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

             cin>>a[i],a[i]+=a[i-];

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

             cin>>h[i];

         ans=tp=;

         s[++tp]=;

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

             d=;

             while(h[s[tp]]>=h[i]){

                 idx=s[tp];          ///最后一个出栈的是最小的

                 tp--;

                 d=a[i-]-a[s[tp]];

                 if(d*h[idx]>ans)ans=d*h[idx];

             }

             s[++tp]=i;

         }

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

     }

 }

巴特西

[单调栈]小A的柱状图

题目描述

输入描述:

输出描述:

输入

输出

说明

备注:

最新文章

热门文章