视频字幕
同学们好！今天我们来挑战一个LeetCode上的经典难题——"接雨水"，题号是42。别看它其貌不扬，这道题可是考察你对数组、双指针、动态规划甚至单调栈理解的"试金石"！作为你们的资深计算机老师，我得告诉你们，这题的解法不止一种，但今天我们要重点解析一个既高效又巧妙的办法——双指针法。这个方法就像武林高手左右互搏，能在O(n)的时间复杂度内解决问题，而且空间复杂度只有O(1)，非常厉害！
首先我们得搞清楚问题是啥。想象一下，给你一堆高高低低的柱子，数组里的数字就是柱子的高度，下雨了，这些柱子之间能积多少水？核心思想是：对于任何一个位置i，它上面能积多少水，取决于它左边最高的柱子高度和右边最高的柱子高度中较矮的那个，再减去当前柱子的高度。比如这个位置5，左边最高是2，右边最高是3，取较矮的2，当前柱子高度是0，所以积水是2减0等于2。如果这个差是负数或零，说明当前柱子比两边最高的矮墙还要高或一样高，那就积不了水。
双指针法能把空间复杂度降到O(1)。它的思想非常巧妙，就像两个人从两头往中间走，一边走一边计算。首先初始化：设置两个指针，left指向数组开头，right指向数组末尾。初始化总水量为0，左边遇到的最高柱子高度为0，右边遇到的最高柱子高度为0。然后是移动策略：当left小于right时，循环继续。在每一步，我们比较height[left]和height[right]。关键判断是：如果height[left]小于height[right]，这意味着当前决定水位高度的短板更有可能在左边，我们就移动左指针。否则移动右指针。
让我们一步步演示双指针法的执行过程。初始状态：left等于0，right等于11，max_left和max_right都是0，总水量是0。第一步：height[0]等于0，height[11]等于1，0小于1，所以移动left指针。第二步：height[1]等于1，height[11]等于1，1大于等于1，所以移动right指针，更新max_right为1。第三步：height[1]等于1，height[10]等于2，1小于2，所以移动left指针，更新max_left为1。第四步：height[2]等于0，height[10]等于2，0小于2，计算积水：max_left减去height[2]等于1减0等于1，总水量变成1。这个过程一直持续到两个指针相遇。
好了，同学们，这道经典的"接雨水"问题，用双指针法是不是感觉豁然开朗？让我们总结一下完整的代码实现。双指针法的精髓在于：在left小于right的循环中，我们总是移动高度较低的那个指针。当移动left时，我们知道height[left]是当前左右两端中较低的那个，而max_left是left左边的最高墙。此时，left位置能接的水量就完全取决于max_left，因为右边至少有height[right]那么高，且height[right]大于height[left]，所以右边的墙肯定够高，不会成为left位置的积水瓶颈。反之亦然。这个巧妙的移动策略避免了对每个位置都去寻找全局的左右最高柱子，从而实现了O(1)的空间复杂度。多画图，多思考那个"为什么总是移动较低的指针"的关键点，你就能彻底掌握它了！