首页 > 其他分享 >acwing131. 直方图中最大的矩形

acwing131. 直方图中最大的矩形

时间:2022-12-01 00:12:04浏览次数:47  
标签:int hh stk 直方图 acwing131 ans 矩形

 

#include "bits/stdc++.h"
using namespace std;
 const int N=1e5+3;
 #define int long long
 int n,a[N];
 int hh,stk[N],w[N];
 
 void sov(){
     hh=0;
     memset(a,0,sizeof a);
     stk[n+1]=w[n+1]=0;
     int i,ans=0;
     
     for(i=1;i<=n;i++) cin>>a[i];
     for(i=1;i<=n+1;i++){
         int t=0;
         while(hh>0&&stk[hh]>=a[i]){
             t+=w[hh];
             ans=max(ans,t*stk[hh]);
             hh--; 
         }
         stk[++hh]=a[i]; w[hh]=t+1;
     }
     cout<<ans<<endl;
 }
  main(){
     while(cin>>n,n) sov();
 }
 

 

标签:int,hh,stk,直方图,acwing131,ans,矩形
From: https://www.cnblogs.com/towboa/p/16940215.html

相关文章

  • 矩形有交问题—CDQ
    矩阵覆盖问题-CDQ分治[COCI2018-2019#2]Sunčanje题目描述Slavko做了一个不寻常的梦。在一个晴朗的早上,\(N\)个白色的矩形一个接着一个爬上了Slavko家的屋顶,并在屋......
  • BMP 图像文件解析及直方图均衡化算法(Java)
    BMP图像解析,基本照抄关于Java读取和编写BMP文件的总结直方图均衡化没抄着,自己写了一个。代码结构:GUI:JavaSwing实现importUtils.BMPImage;importUtils.GraphUti......
  • 四根长度为3、两根长度为4、四根长度为7的木棍能围成多少种不同的矩形
    四根长度为3、两根长度为4、四根长度为7的木棍能围成多少种不同的矩形问题四根长度为3、两根长度为4、四根长度为7的木棍能围成多少种不同的矩形。无需每次用完所有木棍......
  • opencv 矩形标记
     importcv2fromPILimportImageimportpytesseractimportpyautoguiimportnumpyasnpimporttime#图片路径img=cv2.imread('Images/CAD2.png')xstart,......
  • elasticsearch 之 histogram 直方图聚合
    目录1.简介2.bucket_key如何计算3.有一组数据,如何确定是落入到那个桶中4、需求4.1准备mapping4.2准备数据5、histogram聚合操作5.1、根据response_time聚合,间隔为55.1......
  • 2142. 最小矩形覆盖
    题目链接2142.最小矩形覆盖已知平面上不共线的一组点的坐标,求覆盖这组点的面积最小的矩形。输出矩形的面积和四个顶点的坐标。输入格式第一行包含一个整数\(n\),表示......
  • canvas绘制圆角矩形
     canvas绘制圆角矩形Canvas并没有提供绘制圆角矩形的方法,但是通过观察,我们可以发现,其实我们可以将圆角矩形分为四段,可以通过使用arcTo来实现我们假设起点为x,y.绘......
  • 84.柱状图中最大的矩形 largest-rectangle-in-histogram
    问题描述84.柱状图中最大的矩形解题思路首先,要找最大矩形,即要找每个heights[i]所能构成的矩形面积的最大值:heights[i]所能构成的最大矩形,左侧,右侧必定都是连续的大于......
  • 【热力】基于matlab模拟矩形板上二维温度分布
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,matlab项目合作可私信。......
  • 使用Python生成直方图
    1.引言你想知道如何在Python中生成直方图吗?在本教程中,我将向大家展示如何做到这一点。数值数据的分布可以用直方图表示。直方图是数据的一种可视化表示,它使用不同高度的条......