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;
}
京公网安备 11010502036488号