[LCD4][双指针]42. Trapping Rain Water

1. 分析题目

题目给定一个非负整数数组，表示一个高度图，每个宽度为1的柱子代表一段高度。需要计算下雨后这个高度图能够捕获多少水。这是一道典型的数组和双指针问题，关键在于理解如何有效地计算每个位置上能够捕获的雨水量。

2. 解释思路

本题的核心思路是利用双指针技术来遍历整个数组，同时计算每个位置上可能的蓄水量。可以想象，对于数组中的每个位置，能够蓄水的量取决于其左右两边最高柱子的较小值（决定水面高度）与当前位置的柱子高度的差值。

• 双指针初始化：左指针l和右指针r分别初始化为数组的起始和终止位置。
• 左右最大高度：分别记录左边和右边遇到的最大高度leftMax和rightMax。
• 移动条件：当左边的最大高度小于右边时，移动左指针；否则，移动右指针。
• 蓄水计算：每次移动时，更新当前指针对应的最大高度，并计算当前位置能够蓄水的量，累加到结果中。

3. 解释代码

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        l, r = 0, len(height) - 1  # 初始化左右指针
        leftMax, rightMax = height[l], height[r]  # 初始化左右最大高度
        res = 0  # 初始化结果
        while l < r:  # 当左右指针未相遇时
            if leftMax < rightMax:  # 如果左边最大高度小于右边
                l += 1  # 移动左指针
                leftMax = max(leftMax, height[l])  # 更新左边最大高度
                res += leftMax - height[l]  # 累加蓄水量
            else:
                r -= 1  # 移动右指针
                rightMax = max(rightMax, height[r])  # 更新右边最大高度
                res += rightMax - height[r]  # 累加蓄水量
        return res

4. 分析空间复杂度、时间复杂度

• 时间复杂度：O(n)。整个数组只需要遍历一次，每个元素的蓄水量计算都是O(1)的操作。
• 空间复杂度：O(1)。除了输入数组外，只需要常数级别的空间来存储左右指针和左右最大高度等变量。

这个解法有效地利用了双指针的策略来减少不必要的计算，确保每个位置都只被访问一次，从而达到线性时间复杂度。同时，由于不需要额外存储大量数据，也保证了低空间复杂度。