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