42. 接雨水

难度：🔴 Hard | 标签：双指针、动归、单调栈 | 状态：⬜ LeetCode 链接

思路

每个位置能接的水 = min(左侧最高, 右侧最高) - h[i]。

双指针法（最优）：维护 lmax / rmax，每次处理较低一边——因为低的一边的水量只由该侧 max 决定。

代码

class Solution {
public:
    int trap(vector<int>& h) {
        int l = 0, r = h.size() - 1;
        int lmax = 0, rmax = 0, res = 0;
        while (l < r) {
            if (h[l] < h[r]) {
                lmax = max(lmax, h[l]);
                res += lmax - h[l];
                ++l;
            } else {
                rmax = max(rmax, h[r]);
                res += rmax - h[r];
                --r;
            }
        }
        return res;
    }
};

复杂度

• 时间 O(n)，空间 O(1)
• DP 解法：O(n) 时间 O(n) 空间；单调栈：按层累加

易错 / 回顾

• 难点：为何处理较低一边时可直接结算？因为另一侧 max ≥ 当前侧 max
• 单调栈解法是「按行 / 按层」累加，思路完全不同
• 三种解法各练一次（DP、双指针、单调栈），讲项目时可对比