考点：双指针

数据规模 n ≤ 30000 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

• 数据规模：n ≤ 30000
• 元素值域：h_i ≤ 30000（注意整数类型选择，避免溢出）
• 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
• 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：双指针

本题切入点

接雨水：左右双指针维护两侧最高挡板，每次移动较矮的一侧并累加 max(0, 该侧最高 − 当前高度)，O(n) 可扛 n≤30000。

用两个指针协同移动，把两层循环的 O(n²) 优化到 O(n)。

思路框架（双指针 通法 · 非本题专属）

1. 判断是「对撞指针」（一左一右向中间靠拢）还是「快慢指针」（同向不同速）。
2. 确定指针移动的单调条件：什么情况下移动左指针，什么情况下移动右指针。
3. 每一步根据当前指针位置更新答案，直到指针相遇或越界。
4. 常配合有序性使用：无序时先排序。

实现要点：写成 while (l < r) 循环最清晰，切记每轮至少有一个指针移动，否则死循环。

复杂度：时间 O(n)（排序则 O(n log n)） ｜ 空间 O(1)

该范式的通法易错点

• 指针移动条件写反，漏解或死循环。
• 两指针同时移动导致跳过合法解。

对照本题

• 数据规模 n ≤ 30000，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
• 元素值域最大到 30000 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 5 / 1 2 3 4 5 → 输出 10

四个槽位水面高度依次为 1、2、3、4。

样例 2：输入 6 / 3 1 2 5 4 5 → 输出 19

五个槽位水面高度依次为 3、3、3、5、5。