leetcode42: 捕捉雨水 - 输入： height = [4,2,0,3,2,5] 高度 输出：9 小贴士

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

步骤1：定义题目问题性质

计算问题性质

给定一组表示柱子高度的数组 height，每个元素代表柱子的位置和高度。我们的目标是计算雨水在这些柱子之间能够储存的总量。这是典型的“接雨水”问题。

输入输出条件

• 输入：一个非负整数数组 height，长度为 n，每个元素代表宽度为 1 的柱子高度。
• 输出：一个整数，表示可以存储的雨水总量。

限制条件

• n == height.length，数组的长度为 n。
• 1 <= n <= 2 * 10^4，柱子的数量最多为 20000。
• 0 <= height[i] <= 10^5，每个柱子的高度最大为 100000。

边界条件

• 如果 n == 1，显然无法存储任何雨水，结果为 0。
• 如果所有柱子的高度都为 0，同样也不能存储雨水。
• 只有两个柱子的情况下，也不会存储雨水。

步骤2：解题思路分解

这类问题可以从以下几种方法着手：

1. 暴力解法

对每个柱子来说，计算它左右两侧的最大高度，然后根据该柱子的高度，计算其上方可以存储的雨水量。这个解法时间复杂度为 O(n^2)，不够高效，尤其在输入规模较大时。

2. 动态规划

为了避免暴力解法的重复计算，可以提前计算出每个柱子左右两侧的最大高度，使用两个数组 left_max 和 right_max 分别记录到每个柱子为止，左侧和右侧的最大高度。这样就可以在 O(n) 时间内计算每个柱子的存储水量。

• 时间复杂度：O(n)
• 空间复杂度：O(n)（由于使用了两个额外数组）

3. 双指针法（最佳方案）

双指针法通过维护两个指针，一个从左向右，一个从右向左，逐步计算每个位置的存水量。通过比较左右两侧的最大高度，更新指针和存水量。这种方法可以在 O(n) 时间内完成计算，且只需要常数级的额外空间。

• 时间复杂度：O(n)
• 空间复杂度：O(1)（只使用了几个额外的变量）

解决方案总结

最优方法是双指针法，因为它在时间和空间上都达到了最优。

步骤3：C++代码实现

代码解析：

1. 使用 left 和 right 两个指针从数组两端向中间移动。
2. left_max 和 right_max 分别存储左边和右边遇到的最大高度。
3. 每次根据 height[left] 和 height[right] 的大小决定移动哪个指针，并计算对应位置的存水量。
4. 当 left 和 right 相遇时，结束计算。

步骤4：启发与优化

通过这道题可以得到的启发是：

• 双指针法的使用可以极大地提高算法的效率，尤其是在处理类似的对称性问题时，它避免了不必要的计算。
• 空间优化：我们通过双指针法减少了空间复杂度，使得算法可以在不额外存储中间结果的情况下高效完成任务。这种思路对于处理大规模数据集非常有用。

步骤5：实际应用场景分析

这种“接雨水”的问题在实际生活中的应用场景很多，特别是在地理信息系统和建筑水力学中。例如：