题解 | #接雨水问题#

如何用双指针处理接雨水问题？

• 当前柱子能否盛水和桶的高度有关，而桶的高度又由左右两个边界的最少那个决定，因此需要双指针来指向数组的首尾边界。
• 由于柱子能否盛水跟桶的高度有关，所以最短边界的那边才能盛水，因此如果确定了最短边界，就从最短边界那边遍历柱子来确定盛水量，但是如果柱子比边界大就无法盛水了，此时就要更新当前边界，并由当前的两个边界确定新的桶高度，再从新的较低边界那边确定盛水量，如此往复直到两个指针相遇。

参考

https://blog.nowcoder.net/n/cd5a55084e6143bcbe18b83f1cfd4994?f=comment

https://blog.nowcoder.net/n/f47d51aea640480ab45b3f68b444edf5?f=comment

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * max water
 * @param arr int整型一维数组 the array
 * @return long长整型
 */
export function maxWater(arr: number[]): number {
    // write code here
    let water = 0;
    let left = 0;
    let maxL = 0;  // 左边最长的木板宽度
    let maxR = 0;  // 右边最长的木板宽度
    let right = arr.length-1;

    while (left <= right) {
        // 每次更新两边的边界，如果当前柱子比上一次的边界长，则当前柱子充当新的边界，这个柱子的盛水量为0，否则这个柱子的盛水量就是边界减去柱子高度（也就是柱子比边界低时才盛水）
        maxL = Math.max(maxL, arr[left]);
        maxR = Math.max(maxR, arr[right]);
        // 以较短的边界为桶的高度确定当前柱子的盛水量，如果边界比柱子高，当前柱子盛水量为边界减去柱子高度，如果边界比柱子低，当前柱子盛水量为0
        if(maxR > maxL)
            water += maxL - arr[left++];
        else
            water += maxR - arr[right--];
    }

    return water;
}