【数据结构和算法】双指针求接雨水问题，图文结合

1，三指针求解

这题让求柱子中间能盛多少水，首先可以肯定两边的两个柱子是不能盛水的，只有两边之间的柱子有可能会盛水。最简单的一种方式就是使用3个指针，先找到最高的柱子，用一个指针top指向最高柱子，然后最高柱子左边用两个指针，一个left，一个right（这里的left和right指向柱子的高度）。

• 如果left大于right，那么肯定是能盛水的，因为left是小于等于最高柱子top的，并且right指向的柱子是在left和最高柱子top之间，根据木桶原理盛水量由最矮的柱子决定，所以盛水是left-right。

• 如果left不大于right，是不能盛水的，这时候我们要让left等于right。因为right是不能超过最高柱子的，我们增加left的高度，有利于后面计算的时候盛更多的水。
  
  
  
  
  
  代码如下

    public long maxWater(int[] arr) {
        if (arr.length <= 2)
            return 0;
        //找到最高的柱子的下标
        int max = Integer.MIN_VALUE;
        int maxIndex = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
                maxIndex = i;
            }
        }
  
        //统计最高柱子左边能接的雨水数量
        int left = arr[0];
        int right = 0;
        long water = 0;
        for (int i = 1; i < maxIndex; i++) {
            right = arr[i];
            if (right > left) {
                left = right;
            } else {
                water += left - right;
            }
        }
  
        //统计最高柱子右边能接的雨水数量
        right = arr[arr.length - 1];
        for (int i = arr.length - 2; i > maxIndex; i--) {
            left = arr[i];
            if (arr[i] > right) {
                right = left;
            } else {
                water += right - left;
            }
        }
  
        //返回盛水量
        return water;
    }

  看一下运行结果
  

2，双指针求解

这里我们还可以使用双指针，一个指向最左边，一个指向最右边，如下图所示。

这里要明白一点，最开始的时候如果左边柱子从左往右是递增的，那么这些柱子是不能盛水的，比如像下面这样

同理最开始的时候如果右边的柱子从右往左是递增的，也是不能盛水的。所以上面图中right指向的是右边第2根柱子。确定左右两边柱子的的代码如下

int left = 0, right = height.length - 1;
while (left < right && height[left] <= height[left + 1])
    left++;
while (left < right && height[right] <= height[right - 1])
    right--;

通过上面的计算，确定left和right的值之后，在left和right之间相当于构成了一个桶，桶的高度是最矮的那根柱子。然后我们从两边往中间逐个查找，如果查找的柱子高度小于桶的高度，那么盛水量就是桶的高度减去我们查找的柱子高度，如果查找的柱子大于桶的高度，我们要更新桶的高度。我们来看下最终代码

    public long maxWater(int[] arr) {
        if (arr.length <= 2)
            return 0;
        long water = 0;
        int left = 0, right = arr.length - 1;
        //最开始的时候确定left和right的边界，这里的left和right是
        //柱子的下标，不是柱子的高度
        while (left < right && arr[left] <= arr[left + 1])
            left++;
        while (left < right && arr[right] <= arr[right - 1])
            right--;

        while (left < right) {
            int leftValue = arr[left];
            int rightValue = arr[right];
            //在left和right两根柱子之间计算盛水量
            if (leftValue <= rightValue) {
                //如果左边柱子高度小于等于右边柱子的高度，根据木桶原理，
                // 桶的高度就是左边柱子的高度
                while (left < right && leftValue >= arr[++left]) {
                    water += leftValue - arr[left];
                }
            } else {
                //如果左边柱子高度大于右边柱子的高度，根据木桶原理，
                // 桶的高度就是右边柱子的高度
                while (left < right && arr[--right] <= rightValue) {
                    water += rightValue - arr[right];
                }
            }
        }
        return water;
    }

上面有3个while循环，看的有点眼花缭乱，实际上我们还可以把它合并为一个，代码如下

    public long maxWater(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        long water = 0;
        int leftmax = 0;
        int rightmax = 0;
        while (left < right) {
            //确定左边的最高柱子
            leftmax = Math.max(leftmax, arr[left]);
            //确定左边的最高柱子
            rightmax = Math.max(rightmax, arr[right]);
            //那么桶的高度就是leftmax和rightmax中最小的那个
            if (leftmax < rightmax) {
                //桶的高度是leftmax
                water += (leftmax - arr[left++]);
            } else {
                //桶的高度是rightmax
                water += (rightmax - arr[right--]);
            }
        }
        return water;
    }

看一下运行结果

3，双指针代码简化

实际上我们还可以再进一步简化，我们看下下面这个图。此时left和right围成的桶的高度是4，这个时候如果right往左移，那么移动之后这个值是小于4的，也就是小于桶的高度，所以这个时候桶的高度是不变的。假如right往左移之后的值是大于4，比如5，那么桶的高度是要更新的。

我们只要确定桶的高度之后，那么盛水量就好求了。

    public long maxWater(int[] arr) {
        int left = 0, right = arr.length - 1, bucketHeight = 0;
        long water = 0;
        while (left < right) {
            //取height[left]和height[right]的最小值
            int minHeight = Math.min(arr[left], arr[right]);
            //如果最小值minHeight大于桶的高度bucketHeight，要更新桶的高度到minHeight
            bucketHeight = bucketHeight < minHeight ? minHeight : bucketHeight;
            water += arr[left] >= arr[right] ? (bucketHeight - arr[right--]) : (bucketHeight - arr[left++]);
        }
        return water;
    }

我把部分算法题整理成了PDF文档，截止目前总共有900多页，大家可以下载阅读
链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666

如果觉得有用就给个赞吧，还可以关注我的《牛客博客》查看更多的详细题解