给定 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 |