题解 | #接雨水问题#

题目主要信息:

• 给定一个整型数组，数组每个元素表示下图所示的每列灰色柱子高度，数值都是非负数
• 在雨水（图中蓝色部分）不超过边界的情况下，问最多能有多少蓝色的格子
• 数组以外的区域高度视为0

具体思路:

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

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

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

具体过程可以参考下图所示：

代码实现:

class Solution {
public:
    long long maxWater(vector<int>& arr) {
        if(arr.size() == 0) //排除空数组
            return 0;
        long long res = 0;
        int left = 0; //左右双指针
        int right = arr.size() - 1; 
        int maxL = 0; //中间区域的边界高度
        int maxR = 0;
        while(left < right){ //直到左右指针相遇
            maxL = max(maxL, arr[left]); //每次维护往中间的最大边界
            maxR = max(maxR, arr[right]);
            if(maxR > maxL) //较短的边界确定该格子的水量
                res += maxL - arr[left++]; 
            else
                res += maxR - arr[right--];
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，两个指针最多共同遍历整个数组
• 空间复杂度：$O(1)O(1)$，常数个变量，没有额外的辅助空间