开始: 2026-09-30 00:00:00

【集训】专题

结束: 2026-10-03 00:00:00
当前  2026-11-04 13:29:46  类型: IOI  状态: 已经结束 

P1. 柱状图中最大的矩形
描述

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1。求在该柱状图中,能够勾勒出来的矩形的最大面积。

输入

第一行一个整数 n ( 1 \le n \le 10^5 )。

第二行 n 个整数 h_1, h_2, \dots, h_n ( 0 \le h_i \le 10^4 ),表示每个柱子的高度。


输出

一个整数,表示最大矩形面积。

样例

输入

6
2 1 5 6 2 3

输出

10
提示

最大的矩形是以高度为 5 和 6 的两根柱子为底,面积 5 \times 2 = 10 。

- 对于 30% 的数据, n \le 100 。

- 对于 100% 的数据, n \le 10^5 , 0 \le h_i \le 10^4 。


提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交