42. 接雨水：双指针维护两侧最高柱

第 i 个位置能接的雨水由左右最高柱中较低的一侧决定： $\max(0, \min(L_i, R_i) - h_i)$ 。预处理两组最高值可解题，但会消耗 $O(n)$ 空间。

双指针不变量#

使用 left、right 从两端收缩，分别维护 leftMax 和 rightMax。若 leftMax <= rightMax，当前位置左侧的上界已经确定，右侧必然至少有 rightMax，所以可以立即结算 left；反之处理 right。

1
class Solution {
2
public:
3
    int trap(vector<int>& height) {
4
        int n = height.size();
5

6
        int l = 0, r = n - 1;
7
        int lmax = 0, rmax = 0;
8

9
        int res = 0;
10

11
        while(l < r) {
12
            lmax = max(lmax, height[l]);
13
            rmax = max(rmax, height[r]);
14

15
            if(lmax < rmax) {
16
                res += lmax - height[l];
17
                l ++;
18
            }
19
            else {
20
                res += rmax - height[r];
21
                r --;
22
            }
23
        }
24

25
        return res;
26
    }
27
};

时间复杂度为 $O(n)$ ，额外空间为 $O(1)$ 。空数组或只有一个柱子时循环不会执行，答案自然为零。