接雨水问题(官方的解法三：双指针)

Z时代
2024-01-10
分类：技术分享

要求：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例：

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

思路：

其实就是按列求值。关注当前列，其左边最高的墙，右边最高的墙。并关注左右两边最高墙的较矮的墙的高度。

较矮墙的高度高于当前列，存的水量为（较矮的墙的高度-当前列的高度）

较矮墙的高度等于当前列，存的水量为0

较矮墙的高度小于当前列，存的水量为0

另外，两端是肯定存不住水的

publicinttrap(int[] height){
int sum = 0;
//两端不用考虑
for (int i = 1; i < height.length - 2; i++) {
int max_left = 0;
//找到左边最高墙,从当前列从右往左遍历
for (int j = i-1; j >= 0; j--) {
if (height[j] > max_left) {
max_left = height[j];
}
}
int max_right = 0;
//找出右边最高墙，从当前列从左往右遍历
for (int j = i+1; j < height.length; j++) {
if (height[j] > max_right) {
max_right = height[j];
}
}
//比较两端最高墙，找出较矮的墙
int min = Math.min(max_left, max_right);
if (min > height[i]) {
sum += (min - height[i]);
}
}
return sum;
}

动态规划进行优化

用max_left[i]代表第i列左边最高墙的高度，max_right[i]代表第i列右边最高墙的高度。实际上，max_left[i]=max(max_left[i-1], height[i-1]), max_right[i] = max(max_right[i+1], height[i+1])

这样就不用每次都要在循环中重新求一次max_left和max_right了。但依旧存在缺点，就是需要从左向右遍历，还是需要数组来存储左右两边的最大墙。

publicinttrap(int[] height){
int sum = 0;
int[] max_left = newint[height.length];
int[] max_right = newint[height.length];
for (int i = 1; i < height.length-1; i++) {
max_left[i] = Math.max(max_left[i-1], height[i-1]);
}
for (int i = height.length-2; i >= 0; i--) {
max_right[i] = Math.max(max_right[i+1], height[i+1]);
}
for (int i = 1; i < height.length - 1; i++) {
int min = Math.min(max_left[i], max_right[i]);
if (min > height[i]) {
sum += (min-height[i]);
}
}
return sum;
}

双指针的改进：

在本题中，max_left[i]和max_right[i]其实都只使用过一次，所以可以使用双指针交替前进，避免数组的使用。已知max_left = Math.max(max_left, height[i-1]),即height[left-1]是可能成为max_left的，所以只要height[left-1]<height[right+1],那么max_left就一定是小于max_right的。

此处，left代表左侧指针的索引，right代表右侧指针的索引。只要max_left<max_right,就从左往右更新，因为较矮的墙会在左侧更新，否则就从右往左更新。

publicinttrap(int[] height){
int sum = 0;
int max_left = 0;
int max_right = 0;
int left = 1;//左指针
int right = height.length - 2;//右指针
for (int i = 1; i < height.length - 1; i++) {
//从左到右更新
if (height[left-1] < height[right+1]) {
max_left = Math.max(max_left, height[left-1]);
int min = max_left;
if (min > height[left]) {
sum += (min-height[left]);
}
left++;
} else {//从右往左更新
max_right = Math.max(max_right, height[right+1]);
int min = max_right;
if (min > height[right]) {
sum += (min - height[right]);
}
right--;
}
}
return sum;
}