| 题目名称 | 3454. [POJ 2559]直方图中最大的矩形 |
|---|---|
| 输入输出 | histogram.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 64 MiB |
| 测试数据 | 1 |
| 题目来源 |
 增强型图元文件
于2020-08-26加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：12， 提交：24， 通过率：50% | ||||
 ┭┮﹏┭┮ |
100 | 0.030 s | 6.50 MiB | C++ |
|
ムラサメ |
100 | 0.031 s | 7.41 MiB | C++ |
|
yrtiop |
100 | 0.032 s | 4.27 MiB | C++ |
|
sywgz |
100 | 0.087 s | 5.74 MiB | C++ |
|
锝镆氪锂铽 |
100 | 0.099 s | 13.66 MiB | C++ |
|
sywgz |
100 | 0.103 s | 5.74 MiB | C++ |
|
sywgz |
100 | 0.113 s | 5.74 MiB | C++ |
|
sywgz |
100 | 0.114 s | 5.74 MiB | C++ |
|
00000 |
100 | 0.118 s | 8.03 MiB | C++ |
 已注销 |
100 | 0.118 s | 15.95 MiB | C++ |
| 关于 直方图中最大的矩形 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
丹钓站~~(用printf输出longlong一定要用lld !!!!!!!!!)
| ||||
|
正解单调栈，记得开long long
| ||||
|
本题只有一个测试数据，基本涵盖了所有可能的陷阱。
提醒：请自行估计数据范围  增强型图元文件
2020-08-26 22:35
1楼
| ||||
【题目描述】
本题中的直方图是由在公共基准线上对齐的一系列矩形组成的多边形。 矩形的宽度相等，但高度可以不同。 例如，左图显示了直方图，该直方图由高度为2、1、4、5、1、3、3的矩形组成，矩形的宽度为单位1。
通常，直方图用于表示离散分布，例如，文本中字符的频率。 需要注意的是矩形的顺序，即它们的高度，这是非常重要的。计算面积直方图中与公共基线对齐的最大矩形。 右图显示了所描绘的直方图的最大对齐矩形。
简明题意：如图所示，在一条水平线上有n个宽为1的矩形，求包含于这些矩形的最大子矩形面积（图中的阴影部分的面积即所求答案）。
【输入格式】
有多组测试数据，每组数据占一行。输入零时读入结束。
每行开头为一个数字n（1<=n<=10^5）,接下来在同一行给出n个数字h1,h2,...,hn（0<=hi<=10^9）表示每个矩形的高度。
最后以单独的一个零结束。
【输出格式】
对于每组数据，输出最大子矩阵面积，一组数据输出一行。
【样例输入】
7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0
【样例输出】
8 4000
【提示】
注：本题只有一个测试数据，该测试数据包含所有的可能的陷阱
【来源】
《算法竞赛进阶指南》