🌳 题目描述：

题目内容

小羊有 n 个插在数轴上的木板，其中第 i 块木板高度为 a，相邻木板之间的宽度为 1，木板本身的宽度忽略不计。 现在小羊要使用这 n 个木板来接雨水，他想知道如果他可以提前调整这些木板的排列顺序，那么最多可以接多少雨水?

输入描述

第一行输入一个整数 n（2 ≤ n ≤ 2 *$10^5$）代表数组中的元素数量。

第二行输入 n 个整数 a1, a2,..., an (1 ≤ ai ≤$10^9$) 表示每块木板的高度。

输出描述

在一行上输出一个整数，代表在任意排列所有木板后，可以接到雨水的最大量。

样例1

样例 1:

输入
4
1 3 4 5

输出
12

🕵🏽 面试评估：

这道题是经典的接雨水问题，考察候选人的理解能力。最大的蓄水量高度取决次高的木板长度，如果能够快速的找到这个要点就能轻松解决这道问题。

🧗难度系数：

⭐️ ⭐️

提示

思路分析，题解，代码，复杂度分析仅对算法/后端训练营用户开放