牛客小白月赛13-H（单调栈+树状数组）

题目链接：https://ac.nowcoder.com/acm/contest/549/H

题意：给一个柱状图，包括每个矩阵的宽度和高度，求能组成的最大矩阵的面积。

思路：显然最大矩阵的高一定为n个矩阵中的一个矩阵的高，所以不访用单调栈求出每个矩阵左边、右边第一个高度小于该矩阵的下标。然后用树状数组求出该区间的宽度和，遍历一遍即可得到结果。算法复杂度O(nlogn)，顺便吐槽这题数据，一朋友没用单调栈暴力求区间，复杂度为O(n^2)，竟然也过了。。

AC代码：

#include<cstdio> using namespace std; typedef long long LL; const int maxn=1000005;int n,p; int h[maxn],stk[maxn],L[maxn],R[maxn]; LL tr[maxn],ans;int lowbit(int x){return x&(-x); }void update(int x,int num){while(x<=n){tr[x]+=num;x+=lowbit(x);} }int query(int x){int ans=0;while(x>0){ans+=tr[x];x-=lowbit(x);}return ans; }int main(){scanf("%d",&n);for(int i=1;i<=n;++i){int tmp;scanf("%d",&tmp);update(i,tmp);}for(int i=1;i<=n;++i)scanf("%d",&h[i]);h[0]=h[n+1]=0;stk[p=0]=0;for(int i=1;i<=n;++i){while(h[stk[p]]>=h[i]) --p;L[i]=stk[p]+1;stk[++p]=i;}stk[p=0]=n+1;for(int i=n;i>=1;--i){while(h[stk[p]]>=h[i]) --p;R[i]=stk[p]-1;stk[++p]=i;}for(int i=1;i<=n;++i){int w=query(R[i])-query(L[i]-1);if(1LL*w*h[i]>ans) ans=1LL*w*h[i];}printf("%lld\n",ans);return 0; }

 

转载于:https://www.cnblogs.com/FrankChen831X/p/10808617.html

新人创作打卡挑战赛发博客就能抽奖！定制产品红包拿不停！

总结

以上是生活随笔为你收集整理的牛客小白月赛13-H（单调栈+树状数组）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。