【力扣刷题】42. 接雨水-双指针

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

思路1：[BoyanLu](https://leetcode.cn/u/LuBoyan/)：如果 height\[left\] < height\[right\]，则计算leftMax-height\[l\]为该点的答案，可以这么理解：
当前左指针指向的地方记为点a，在右侧至少有一点b大于a，接雨水的高度是由点a左右两侧较小的那方决定，那么a左侧的最大值一定不是全局最大值，由leftMax-height\[l\]即可得到a点的雨水高度。同理 height\[left\] >= height\[right\]时，对右侧同样成立。

class Solution {
public:
    int trap(vector<int>& height) {
        int l=0,r=height.size()-1;
        int lm=0,rm=0,ma=0;
        int ans=0;
        while(l<r){
            lm=max(lm,height[l]);
            rm=max(rm,height[r]);
            if(lm>rm){
                ans+=rm-height[r];
                r--;
            }else{
                ans+=lm-height[l];
                l++;
            }
        }
        return ans;
    }
};

思路2：[威小汪💦](https://leetcode.cn/u/wei-xiao-wang/)：试想被水填满后的情况，最高柱子左侧水位必然是递增的，右侧水位必然是递减的，不可能出现中间有凹的情况（凹会被水填满）。于是只要找到最高柱子的位置，左侧一次正向遍历，右侧一次反向遍历，即可实时计算水位并累计水位高度差作为积水量。

class Solution {
public:
    int trap(vector<int>& height) {
        int maxHeight = 0;
        int maxHeightPos = -1;
        for (int i=0;i<height.size();i++) {
            if (height[i] > maxHeight) {
                maxHeight = height[i];
                maxHeightPos = i;
            }
        }
        if (maxHeightPos == -1) return 0;
        int waterHeight = 0;
        int waterSum = 0;
        for (int i=0;i<maxHeightPos;i++) {
            // 左侧水位
            if (height[i] > waterHeight) waterHeight = height[i];
            waterSum += waterHeight - height[i];
        }
        waterHeight = 0;
        for (int i=height.size()-1;i>maxHeightPos;i--) {
            // 右侧水位
            if (height[i] > waterHeight) waterHeight = height[i];
            waterSum += waterHeight - height[i];
        }
        return waterSum;
    }
};