A7240. 水瓶挑战
编程题
普及-
知识点
题目描述
$Sherry$ 是一位科学爱好者，她在武陵实验室里有一个长长的玻璃容器，容器里放置了 $n$ 块高度不同的隔板，这些隔板之间的距离都是 $1$。每块隔板的高度分别为 $h_i$，隔板的厚度不计。
$Sherry$ 想通过选择任意两块隔板，在它们之间的区域注水。她希望选中的区域能够存储尽可能多的水。
水能存储的体积由公式计算：两个隔板高度的最小值 $\times$ 两个隔板间的距离。$Sherry$ 需要计算出，在所有可能的隔板组合中，最大可以存储多少水。
$Sherry$ 想通过选择任意两块隔板，在它们之间的区域注水。她希望选中的区域能够存储尽可能多的水。
水能存储的体积由公式计算：两个隔板高度的最小值 $\times$ 两个隔板间的距离。$Sherry$ 需要计算出，在所有可能的隔板组合中，最大可以存储多少水。
输入格式
第一行输入一个整数 $n$，表示有 $n$ 块隔板。
第二行输入 $n$ 个整数 $h_1, h_2, ..., h_n$，表示每块隔板的高度。
第二行输入 $n$ 个整数 $h_1, h_2, ..., h_n$，表示每块隔板的高度。
输出格式
输出一个整数，表示所有区域中最多可以存多少水。
输入输出样例
输入 #1
9 1 8 6 2 5 4 8 3 7
输出 #1
49
说明/提示
### 样例解释
图中垂直线代表输入数组 $[1,8,6,2,5,4,8,3,7]$。
在此情况下，容器能存的水（表示为蓝色部分）的最大值为 $min(8,7)*(9-2)=49$，这里的 $9-2$ 是隔板间的距离。
### 数据范围
对于 $100\%$ 的数据，满足 $1 \leq h _ i \leq 10 ^ 9,2 \leq n \leq 10^5$。
图中垂直线代表输入数组 $[1,8,6,2,5,4,8,3,7]$。
在此情况下，容器能存的水（表示为蓝色部分）的最大值为 $min(8,7)*(9-2)=49$，这里的 $9-2$ 是隔板间的距离。
### 数据范围
对于 $100\%$ 的数据，满足 $1 \leq h _ i \leq 10 ^ 9,2 \leq n \leq 10^5$。