题解 | #接雨水问题#

1.方法：双指针

知识点：双指针

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个指针（特殊情况甚至可以多个），两个指针或是同方向访问两个链表、或是同方向访问一个链表（快慢指针）、或是相反方向扫描（对撞指针），从而达到我们需要的目的。

思路：

我们都知道水桶的短板问题，控制水桶水量的是最短的一条板子。这道题也是类似，我们可以将整个图看成一个水桶，两边就是水桶的板，中间比较低的部分就是水桶的底，由较短的边控制水桶的最高水量。但是水桶中可能出现更高的边，比如上图第四列，它比水桶边还要高，那这种情况下它是不是将一个水桶分割成了两个水桶，而中间的那条边就是两个水桶的边。

有了这个思想，解决这道题就容易了，因为我们这里的水桶有两个边，因此可以考虑使用对撞双指针往中间靠。

具体做法：

• step 1：检查数组是否为空的特殊情况
• step 2：准备双指针，分别指向数组首尾元素，代表最初的两个边界
• step 3：指针往中间遍历，遇到更低柱子就是底，用较短的边界减去底就是这一列的接水量，遇到更高的柱子就是新的边界，更新边界大小。

class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        // write code here
        //排除空数组
        int n = arr.size();
        if(n == 0)
            return 0;
        //左右双指针    
        int left = 0;
        int right = n-1;
        long long res = 0;
        //中间区域的边界高度
        int maxL = 0;
        int maxR = 0;
        //直到左右指针相遇
        while(left < right)
        {
            //每次维护往中间的最大边界
            maxL = max(maxL,arr[left]);
            maxR = max(maxR,arr[right]);
            //用较短的边界确定该格子的水量
            /*
            对于较短的边，继续往里面进行遍历，直到遇到比另一条边还高的边，否则就一直遍历。因为如果不比另一边高，则没有必要换边往里面遍历，否则还是用这条短边计算盛水量
            在往里收缩时，如果当前边比边界更短，则可以盛水，盛水量为较短边减去该边，如果大，则边界更新为该值，相减结果为0，盛水量就为0
            */
            if(maxL > maxR)
                res += maxR - arr[right--];
            else
                res += maxL - arr[left++];
        }
        return res;
    }
};