1,三指针求解

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

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

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

      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,双指针求解

这里我们还可以使用双指针,一个指向最左边,一个指向最右边,如下图所示。
image.png
这里要明白一点,最开始的时候如果左边柱子从左往右是递增的,那么这些柱子是不能盛水的,比如像下面这样
image.png
同理最开始的时候如果右边的柱子从右往左是递增的,也是不能盛水的。所以上面图中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--;

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

    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,那么桶的高度是要更新的。
image.png
我们只要确定桶的高度之后,那么盛水量就好求了。

    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

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