首页 > 试题广场 >

小A的柱状图

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



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


输出描述:
一行一个整数，表示最大的矩形面积
示例1

输入

7
1 1 1 1 1 1 1
2 1 4 5 1 3 3

输出

8

说明

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

备注:
算法知识视频讲解
开通博客
头像 Kur1su
发表于 2020-07-23 16:28:56
Description 柱状图是有一些宽度相等的矩形下端对齐以后横向排列的图形，但是小A的柱状图却不是一个规范的柱状图，它的每个矩形下端的宽度可以是不相同的一些整数，分别为a[i]a[i],每个矩形的高度是h[i]h[i],现在小A只想知道，在这个图形里面包含的最大矩形面积是多少。 Solutio 展开全文
去ta的博客 赞 (7) 回复(0) 收起
头像 zzugzx
发表于 2020-07-23 18:52:27
题目链接 题意：题解： 图片来源 void build(int n) { top = 0; for(int i = 0; i < n; i++) { int k = top; while (k > 0 && a[s 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 sunrise__sunrise
发表于 2020-07-23 14:28:48
问题描述 Solution Code // 单调栈 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 lifehappy
发表于 2020-07-23 18:05:48
小A的柱状图 思路 经典的单调栈题目，对于每一个位置，我们维护他以当前高度可以到达的最左方，以及他当前高度可以到达的最有方，显然就有以他的高度的矩形块的面积就出来了，所以我们只需要统计n个矩形的最大值就行。 具体细节操作看代码注释。 代码 /* Author : lifehappy */ #pr 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 凝舞の
发表于 2020-07-24 15:07:26
题目链接小A的柱状图题意这是一个简单的单调栈问题，对于每一个矩形我们可以找出其能够到达的最远位置，所以只需要枚举n个矩形的最大值就ok啦~ #include<bits/stdc++.h> typedef long long ll; const int maxn =1e6+5; using 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 夜空的弧光灯
发表于 2022-07-12 01:33:59
小A的柱状图 题目描述 柱状图是有一些宽度相等的矩形下端对齐以后横向排列的图形，但是小A的柱状图却不是一个规范的柱状图，它的每个矩形下端的宽度可以是不相同的一些整数，分别为a[i]a[i],每个矩形的高度是h[i]h[i],现在小A只想知道，在这个图形里面包含的最大矩形面积是多少。 ![在这里插入 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 dilingtian
发表于 2022-11-06 01:00:33
本题是找一个最大面积的矩形，图形是不能变换的，所以我们只需要先确定左右区间，再得到本区间的最小高度便可得到面积。我们可以通过栈的特点，确定第i个位置上的左端点和右端点，高度为h[i]。h[i]。h[i]。 当我们遍历到第i个位置时，我们以h[i]h[i]h[i]为矩形高度，对于左右端点而言，增加高度 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 冷云___
发表于 2024-01-29 21:14:02
链接：https://ac.nowcoder.com/acm/contest/22669/Q 来源：牛客网 柱状图是有一些宽度相等的矩形下端对齐以后横向排列的图形，但是小A的柱状图却不是一个规范的柱状图，它的每个矩形下端的宽度可以是不相同的一些整数，分别为a[i],每个矩形的高度是h[i],现在小 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 罗hao
发表于 2022-06-29 16:30:37
我用栈来存每个矩形的下标，而不是高度或者宽度。 #include<bits/stdc++.h> using namespace std; struct node{ int d,h; }a[1000001]; long long maxx(long long a,long long 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 hnust_yangyanjun
发表于 2020-07-27 23:02:48
题意：给你一个柱状图，有n根柱子，给予你每根的宽度和高度，求柱状图的最大矩形面积？ 思路：单调栈，维护一个单调递增的栈，维护高度和左边界。当h[i]>栈顶元素的高度时入栈，左边界不变。当h[i]<栈顶元素的高度时，栈顶元素出栈，并计算以该栈顶元素高度为一条边的矩形最大面积（既（右边界-左 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

枚举
难度：
0条回答 8浏览

热门推荐

相关试题

小A的柱状图

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号