#头条创作挑战赛#

大家好，今天给大家分享一道经典面试题接雨水（trapping-rain-water）。

题目要求：

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

难度： 困难

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]

输出：9

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

题解：

关键思想：双指针。

我们可以使用两个指针，一个指向左边的柱子，一个指向右边的柱子。然后我们可以逐渐将指针向中间移动，同时维护左边和右边的最大高度。在移动指针的过程中，如果左边的最大高度小于右边的最大高度，则说明左边可以接到水，反之则说明右边可以接到水。我们可以将左边或右边的指针向中间移动一步，并将左边或右边的最大高度更新为当前指针所指的柱子高度。

下面是具体的算法步骤：

1. 初始化左指针left=0，右指针right=n-1，左边最大高度left_max=0，右边最大高度right_max=0，水的容量volume=0。
2. 当left<=right时，执行以下步骤： a. 如果left_max<right_max，则说明左边可以接到水，计算当前位置能接的水量并加入volume，然后将左指针向中间移动一步，同时更新左边最大高度left_max。 b. 否则，右边可以接到水，计算当前位置能接的水量并加入volume，然后将右指针向中间移动一步，同时更新右边最大高度right_max。
3. 返回水的容量volume。

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    // 初始化左指针left=0，
    // 右指针right=n-1，
    // 左边最大高度left_max=0，
    // 右边最大高度right_max=0，
    // 水的容量volume=0。
    let n = height.length, left = 0, right = n - 1, left_max = 0, right_max = 0, volume = 0;
    while (left <= right) {
        // 如果left_max<right_max，则说明左边可以接到水，
        // 计算当前位置能接的水量并加入volume，
        // 然后将左指针向中间移动一步，
        // 同时更新左边最大高度left_max。
        if (left_max < right_max) {
            // 更新左边最大高度left_max
            left_max = Math.max(left_max, height[left]);
            // 计算当前位置能接的水量
            volume += Math.max(0, left_max - height[left]);
            // 将左指针向中间移动一步
            left++;
        } else {
            // 右边可以接到水，计算当前位置能接的水量并加入volume，
            // 然后将右指针向中间移动一步，同时更新右边最大高度right_max。
            // 更新右边最大高度right_max。
            right_max = Math.max(right_max, height[right]);
            // 计算当前位置能接的水量
            volume += Math.max(0, right_max - height[right]);
            // 将右指针向中间移动一步
            right--;
        }
    }
    // 返回水的容量
    return volume;
}

代码执行结果如下：

上述解法时间复杂度为O(n)，空间复杂度为O(1)。

如果你有其它解答思路，欢迎评论区留言讨论。