[单调栈]小A的柱状图
链接：https://ac.nowcoder.com/acm/problem/23619
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
空间限制：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≤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
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int amn=1e6+5; 5 ll a[amn],h[amn],s[amn]; 6 int main(){ 7 ll n,tp,d,ans,idx; 8 while(cin>>n){ 9 a[0]=0; 10 for(int i=1;i<=n;i++) 11 cin>>a[i],a[i]+=a[i-1]; 12 for(int i=1;i<=n;i++) 13 cin>>h[i]; 14 ans=tp=0; 15 s[++tp]=0; 16 for(int i=1;i<=n;i++){ 17 d=0; 18 while(h[s[tp]]>=h[i]){ 19 idx=s[tp]; ///最后一个出栈的是最小的 20 tp--; 21 d=a[i-1]-a[s[tp]]; 22 if(d*h[idx]>ans)ans=d*h[idx]; 23 } 24 s[++tp]=i; 25 } 26 printf("%lld\n",ans); 27 } 28 }
查看8道真题和解析
