42. 接雨水#

public int trap(int[] height) {
    // totalWater 用于累计所有位置最终能接到的雨水总量
    int totalWater = 0;

    // 遍历每个位置（除去两端）
    // 两端无法形成“左右挡板”，一定不能积水，因此从 1 到 length-2
    for (int i = 1; i < height.length - 1; i++) {
        // leftMax 记录当前位置 i 左侧（含 i）能看到的最高柱子
        int leftMax = 0;
        // rightMax 记录当前位置 i 右侧（含 i）能看到的最高柱子
        int rightMax = 0;

        // 找出左边最高的柱子
        // j 从最左端扫到 i，不断更新 leftMax
        for (int j = 0; j <= i; j++) {
            leftMax = Math.max(leftMax, height[j]);
        }

        // 找出右边最高的柱子
        // j 从 i 扫到最右端，不断更新 rightMax
        for (int j = i; j < height.length; j++) {
            rightMax = Math.max(rightMax, height[j]);
        }

        // 计算当前位置能积的水
        // 当前位置水位由左右最高柱子的较小值决定，再减去当前柱高
        totalWater += Math.min(leftMax, rightMax) - height[i];
    }

    // 返回总积水量
    return totalWater;
}

第一次遍历（计算leftMax）：
leftMax[0] = 3
leftMax[1] = max(3,1) = 3
leftMax[2] = max(3,2) = 3
leftMax[3] = max(3,4) = 4

第二次遍历（计算rightMax）：
rightMax[3] = 4
rightMax[2] = max(4,2) = 4
rightMax[1] = max(4,1) = 4
rightMax[0] = max(4,3) = 4

第三次遍历（计算积水）：
位置1：min(3,4) - 1 = 2
位置2：min(3,4) - 2 = 1
总积水 = 3

public int trap(int[] height) {
    // 边界条件：空数组或柱子少于 3 根时，无法形成凹槽积水
    if (height == null || height.length <= 2) return 0;

    // n 表示柱子总数，便于后续复用
    int n = height.length;
    // leftMax[i] 表示下标 i 左侧（含 i）最高柱子高度
    int[] leftMax = new int[n];
    // rightMax[i] 表示下标 i 右侧（含 i）最高柱子高度
    int[] rightMax = new int[n];

    // 计算每个位置左边的最大高度
    // 第一个位置左侧最高值只能是自己
    leftMax[0] = height[0];
    for (int i = 1; i < n; i++) {
        // 当前位置左侧最高 = 前一位置左侧最高 与 当前高度 取较大值
        leftMax[i] = Math.max(leftMax[i-1], height[i]);
    }

    // 计算每个位置右边的最大高度
    // 最后一个位置右侧最高值只能是自己
    rightMax[n-1] = height[n-1];
    for (int i = n-2; i >= 0; i--) {
        // 当前位置右侧最高 = 后一位置右侧最高 与 当前高度 取较大值
        rightMax[i] = Math.max(rightMax[i+1], height[i]);
    }

    // 计算总积水量
    // totalWater 累加每个位置的积水
    int totalWater = 0;
    for (int i = 1; i < n-1; i++) {
        // 每个位置积水 = 左右最大值中的较小者 - 当前高度
        totalWater += Math.min(leftMax[i], rightMax[i]) - height[i];
    }

    // 返回总积水量
    return totalWater;
}

public int trap(int[] height) {
    // left 从左端出发，right 从右端出发
    int left = 0, right = height.length - 1;
    // leftMax 记录 left 扫描过程中见到的最高柱子
    // rightMax 记录 right 扫描过程中见到的最高柱子
    int leftMax = 0, rightMax = 0;
    // totalWater 用于累加所有已确定位置的积水
    int totalWater = 0;

    // 当左右指针未相遇时，区间内仍有位置需要计算
    while (left < right) {
        // 更新左右最大高度
        // 先更新，再计算，保证使用的是“到当前位置为止”的最高值
        leftMax = Math.max(leftMax, height[left]);
        rightMax = Math.max(rightMax, height[right]);

        // 选择较小的一边计算积水
        // 若 leftMax < rightMax，说明 left 侧水位已被 leftMax 限定，可安全结算 left 位置
        if (leftMax < rightMax) {
            // left 位置可积水 = leftMax - 当前高度
            totalWater += leftMax - height[left];
            // 结算完成，left 右移处理下一个位置
            left++;
        } else {
            // 否则 right 侧较小（或相等），可安全结算 right 位置
            // right 位置可积水 = rightMax - 当前高度
            totalWater += rightMax - height[right];
            // 结算完成，right 左移处理下一个位置
            right--;
        }
    }

    // 返回累计的总积水量
    return totalWater;
}