两边夹的应用

今天无意间看到一个算法题，给一组非负整数表示的高程图，每个高程宽度都为 1，问下雨后，会有多少积水。示意图如下：

灰色部分就是高程图中各个位置的高度，用数组表示为[1, 2, 1, 0, 1, 3, 1, 2]，蓝色部分表示的是积水部分，也就是要求的值。

这个题目第一眼看过来有个很直观的解法，每个高度能存储的水量取决于该高度左右两边的最高高度的较小值与当前位置高度的差。比如数组的第三个元素 1，其左边最高是 2，右边最高是 3，则该高度的储水量就是 2 和 3 较小的一个（也就是 2）再减去该高度（也就是 1）得到 1，这样计算所有位置上的储水量之和就是所要求的结果。

进一步怎么得到左右两边的最大值呢，可以通过从左到右计算左边最大值，从右到左计算右边最大值，左边最高值的规则是第一个位置的左边最大值是其本身，其余位置的左边最大值是其左边相邻元素的左边最大值与该元素本身相比较大的一个。根据该规则可得出每个位置的左边最大值如下，用黑色数字表示：

同理最右边位置的右边最大值是其自身，其余位置的右边最大值是右边相邻位置的右边最大值与该位置高度相比的较大值。可以得到每个位置的右边最大值如下，用粉色数字表示：

最后根据规则得出每个位置最终的最大值，即取左边最大值与右边最大值中的较小值，用绿色数字表示：

最终结果就是绿色值与各位置高度的差值之和。按这个思路的实现代码如下，对于数组为空或元素少于三个的情况无法形成积水区，可直接返回。

public int trap(int[] height) {    int length = height.length;    if (height == null || length < 3) {        return 0;    }    int[] maxLeft = new int[length];    int[] maxRight = new int[length];    for (int i = 0; i < length; i++) {        if (i == 0) {            maxLeft[0] = height[0];            maxRight[length - 1] = height[length - 1];        } else {            maxLeft[i] = Math.max(maxLeft[i - 1], height[i]);            maxRight[length - 1 - i] = Math.max(maxRight[length - i], height[length - 1 - i]);        }    }    int total = 0;    for (int i = 0; i < length; i++) {        total += Math.min(maxLeft[i], maxRight[i]) - height[i];    }    return total;}

但是从这个实现可以看出来，要两次循环，而且需要 2 个额外的数组来存储中间过程，虽然很好理解，但不算是个好的解决方案，那么进一步思考一下，对于每个位置的计算是不是可以更简化一些。

刚才的思路我们想着接雨水，水是从上面落下来的，如果换个思路，这时候我们想成不是下雨，而是在涨水，水位在涨的过程中总是先没过低的位置。这样就可以理解成水从两边开始涨，当水高过左右两边的高度时水就会没过该位置向相邻位置流去，如果相邻位置低水就流入低的地方，如果相邻位置高还得再涨。涨水的过程大家应该都有过体会，是容易想像出这个场景的。

再具体一点来描述这个问题，从最左边及最右边的位置同时开始，比较两个位置高度哪个低，先计算低的一边，左边低就计算左边被水淹没的情况，则计算简化成当前位置左边最大值与当前位置的高度差即是该位置积水量，而当前位置左边最大值的计算方式为，取当前的左边最大值与当前位置高度相比的较大值，左边处理完一个位置则从左向右移动 1。右边的情况也类似处理，如果右边低，则计算简化为当前位置右边最大值与当前位置的高度差即是该位置的积水量，右边最大值的计算方式为，取当前的右边最大值与该位置高度相比的较大值，右边处理完一个位置则从右向左移动 1。这个过程从两边向中间不断夹逼，直到左右相邻（或相遇，多一次计算）。如下图示例，箭头所示则是每次计算的位置：

依据这个思路代码实现如下：

public int trap(int[] height) {    if (height == null || height.length < 3) {        return 0;    }    int total = 0, maxLeft = 0, maxRight = 0;    int leftIndex = 0, rightIndex = height.length - 1;    while (leftIndex < rightIndex) {        if (height[leftIndex] <= height[rightIndex]) {            maxLeft = Math.max(maxLeft, height[leftIndex]);            total += maxLeft - height[leftIndex];            leftIndex++;        } else {            maxRight = Math.max(maxRight, height[rightIndex]);            total += maxRight - height[rightIndex];            rightIndex--;        }    }    return total;}

当然想让代码更短的话，可以用 for 替代 while，这样 leftIndex 和 rightIndex 两个循环中需要用到的变量可以定义在 for 的初始化语句里，使得作用域范围更小，同样的可以把++和--操作合并到 total 赋值语句处，利用了先取值后计算的特性（这个可读性不算太好，而且有些语言不支持++和--操作）。改造后的 while 可以写成：

for (int leftIndex = 0, rightIndex = height.length - 1; leftIndex < rightIndex; )

可以看出，第二种思路下的代码实现明显要高效一些，并且不需要定义计算的中间数组，时间和空间效率都要好于第一种。

这种两边夹的应用场景似乎也不少，后面碰到可以再举例写写。