题目内容

一个柱状图由一排宽度均为 1 的柱子紧密相邻排列而成。给定一个整数数组 heights，数组中的每个非负整数表示对应位置柱子的高度。现在要在这个柱状图中选择一块完整的矩形区域，求该矩形面积能够达到的最大值。

约束条件：柱子的数量不少于 1，不超过 10^5；每根柱子的高度为 0 到 10^4 之间的整数。

输入描述

输入包含一个参数：一个整数数组 heights，其中 heights[i] 表示从左到右第 i 根柱子的高度。

输出描述

返回一个整数，表示能够勾勒出的最大矩形面积。

样例1

输入

5 4 3 2 1

输出

9

说明

柱状图从左到右高度为 5、4、3、2、1。

最大矩形选择第 1 根到第 3 根柱子。这三根柱子的最小高度为 3，宽度为 3，面积为 $3 \times 3 = 9$。

样例2

输入

0

输出

0

说明

只有一根高度为 0 的柱子，矩形的高度只能为 0，宽度为 1。

因此面积为 $0 \times 1 = 0$。

样例3

输入

1 0 2 3

输出

4

说明

柱状图从左到右高度为 1、0、2、3。

高度为 0 的柱子将左右两侧隔开。最大矩形位于右侧，选择第 3 根和第 4 根柱子，矩形高度为 2，宽度为 2，面积为 $2 \times 2 = 4$。