LeetCode 42. 接雨水

◎

本节目标

用双指针和两侧最高值在线确定每个较低侧位置的积水贡献。

这题属于数组与矩阵综合框架。它复用双指针，却要求额外维护两侧已经见过的最高柱子。

查看原题

题意与约束

每根柱子上能积的水由左侧最高柱与右侧最高柱的较小值决定。求所有位置的积水总量。

双向贡献的推导

预处理每个位置左右最高值可以得到答案，但需要线性额外空间。用 left、right 分别从两端向中间移动，并记录 leftMax、rightMax。当左端高度不超过右端时，右边已存在足够高的边界，左端位置的水位只由 leftMax 确定；反之可确定右端贡献。于是每个位置只在其较低侧最高值确定时结算一次。

代码实现

源码每轮更新较低侧的最高值，累加“最高值减当前高度”，再移动该侧指针。它不使用前后缀数组或单调栈。

C++

C++17

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0;
        int right = static_cast<int>(height.size()) - 1;
        int leftMax = 0;
        int rightMax = 0;
        int water = 0;

        while (left < right) {
            if (height[left] <= height[right]) {
                leftMax = max(leftMax, height[left]);
                water += leftMax - height[left];
                left++;
            } else {
                rightMax = max(rightMax, height[right]);
                water += rightMax - height[right];
                right--;
            }
        }
        return water;
    }
};

Python

Python 3

class Solution:
    def trap(self, height: list[int]) -> int:
        left = 0
        right = len(height) - 1
        left_max = 0
        right_max = 0
        water = 0

        while left < right:
            if height[left] <= height[right]:
                left_max = max(left_max, height[left])
                water += left_max - height[left]
                left += 1
            else:
                right_max = max(right_max, height[right])
                water += right_max - height[right]
                right -= 1
        return water

复杂度分析

• 时间复杂度：O(n)，两根指针总共走过每个位置一次。
• 空间复杂度：O(1)，只维护两个最高值和两个指针。

易错点

• 用当前两端较低高度直接当作当前位置水位，却没有维护历史最高值。
• 在较高侧结算贡献；此时另一侧边界不足以保证水位已经确定。
• 把短数组当作特殊的负下标问题；双指针不相遇时自然返回 0。

模式迁移

本题是双指针解题框架的双向贡献迁移：相向移动仍依赖较低侧，但不再寻找一个整体最优值，而是逐位置结算贡献。更多组合型模板可回到本节的数组与矩阵综合框架继续学习。