一、题目

给定 n 个非负整数表示每个宽度为 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 个单位的雨水（蓝色部分表示雨水）。

二、解法

解法1：双指针

思路：对于每个位置，能接的水量 = min(左边最大高度, 右边最大高度) - height[i]。
我们不需要预先计算每个位置的左右最大值，而是用两个指针从两端向中间移动，同时维护左侧最大值 leftMax 和右侧最大值 rightMax。

• 如果 height[left] < height[right]，说明左侧的短板决定了当前左侧位置的水量，更新 leftMax 并计算 left 处的水量，然后 left++。

• 否则，处理右侧。

代码实现：

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    if (height.length < 3) return 0;
    let left = 0, right = height.length - 1;
    let leftMax = 0, rightMax = 0;
    let water = 0;

    while (left < right) {
        if (height[left] < height[right]) {
            // 左边较低，处理左指针
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                water += leftMax - height[left];
            }
            left++;
        } else {
            // 右边较低或相等，处理右指针
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                water += rightMax - height[right];
            }
            right--;
        }
    }
    return water;
};

解法2：动态规划

思路：预先计算每个位置左侧最大值和右侧最大值，然后遍历累加。

代码实现：

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    const n = height.length;
    if (n < 3) return 0;
    const leftMax = new Array(n);
    const rightMax = new Array(n);
    leftMax[0] = height[0];
    for (let i = 1; i < n; i++) {
        leftMax[i] = Math.max(leftMax[i-1], height[i]);
    }
    rightMax[n-1] = height[n-1];
    for (let i = n-2; i >= 0; i--) {
        rightMax[i] = Math.max(rightMax[i+1], height[i]);
    }
    let water = 0;
    for (let i = 0; i < n; i++) {
        water += Math.min(leftMax[i], rightMax[i]) - height[i];
    }
    return water;
};

解法3：单调栈

思路：维护一个递减栈，遇到比栈顶高的柱子时，弹出栈顶并计算积水。

代码实现：

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    const stack = [];
    let water = 0;
    for (let i = 0; i < height.length; i++) {
        while (stack.length && height[i] > height[stack[stack.length - 1]]) {
            const top = stack.pop();
            if (!stack.length) break;
            const distance = i - stack[stack.length - 1] - 1;
            const boundedHeight = Math.min(height[i], height[stack[stack.length - 1]]) - height[top];
            water += distance * boundedHeight;
        }
        stack.push(i);
    }
    return water;
};

三、其他

三种算法时间复杂度都是O(n).这道题是困难难度，我也只大概理解了第一种算法，逻辑还有些模糊，可以慢慢理解。