42. 接雨水

给定 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 * 10^4
• 0 <= height[i] <= 10^5

预先遍历，备忘录优化，动态规划

先遍历计算出leftMax数组和rightMax数组， 其中leftMax存储每个位置左边的最大高度，rightMax存储每个位置右边的最大高度，最后再遍历一次计算每个位置能接到的雨水， 求和即可。计算rightMax时要倒序遍历，因为我们要利用已有结果rightMax[i + 1]来计算rightMax[i]

class Solution {
    public int trap(int[] height) {
        int n = height.length; // 获取数组长度
        if (n == 0) { // 如果数组为空，直接返回 0
            return 0;
        }

        int[] leftMax = new int[n]; // 存储每个位置左边的最大高度
        leftMax[0] = height[0]; // 初始化第一个位置的左边最大高度为自身高度。重点。
        for (int i = 1; i < n; ++i) { // 正序遍历
            leftMax[i] = Math.max(leftMax[i - 1], height[i]); // 计算当前位置的左边最大高度
        }

        int[] rightMax = new int[n]; // 存储每个位置右边的最大高度
        rightMax[n - 1] = height[n - 1]; // 初始化最后一个位置的右边最大高度为自身高度。重点。
        for (int i = n - 2; i >= 0; --i) { // 倒序遍历，因为我们要利用已有结果rightMax[i + 1]来计算rightMax[i]
            rightMax[i] = Math.max(rightMax[i + 1], height[i]); // 计算当前位置的右边最大高度
        }

        int ans = 0; // 存储最终结果，即接雨水的总量
        for (int i = 0; i < n; ++i) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i]; // 计算当前位置能接住的雨水量
        }
        return ans; // 返回接雨水的总量
    }
}

• 时间复杂度：O(n)，其中 n 是数组 height 的长度。计算数组 leftMax 和 rightMax 的元素值各需要遍历数组 height 一次，计算能接的雨水总量还需要遍历一次。
• 空间复杂度：O(n)，其中 n 是数组 height 的长度。需要创建两个长度为 n 的数组 leftMax 和 rightMax。

相向指针，贪心

单指针变双指针。

一边遍历一边计算，最后求和，这是线性问题，即整体等于局部之和。

r_max是right右边的最高柱子，不是left右边的。 我们只在乎 min(l_max, r_max)。 我们已经知道 l_max < r_max 了，至于这个 r_max 是不是右边最大的，不重要。重要的是 height[i] 能够装的水只和较低的 l_max 之差有关

本质上是贪心，或者是上面动态规划解法的滚动更新版

双指针解法的本质是求和对顺序不敏感，所以我们改变了求和的顺序， 预先遍历解法中是先顺序和倒序遍历两次以初始化两个高度数组，再顺序遍历一次以求和。双指针解法是一左一右地遍历，边走边算。

// 本质上是贪心，是上面动态规划解法的滚动更新版
class Solution {
    public int trap(int[] height) {
        int ans = 0; // 用于存储最终结果，即接雨水的总量
        int left = 0, right = height.length - 1; // 初始化左右指针
        int leftMax = 0, rightMax = 0; // 初始化左右两边的最大高度

        // 使用双指针遍历数组。收敛序列，求和顺序无所谓，所以可以交叉求和。
        while (left < right) {
            // 更新[0,left]中的最大高度
            leftMax = Math.max(leftMax, height[left]);
            // 更新[right,n]中的最大高度
            rightMax = Math.max(rightMax, height[right]);

            // 判断左右指针指向的高度，leftMax < rightMax 说明 leftMax > height[left] (< leftMax) < rightMax，
            // 即 left 是极小值点，所以要计算 left 处接到的雨水量。虽然left和rightMax之间还有一个right，且我们不知道height[right]的高度，但是无所谓，
            // 因为height[right]一定小于rightMax。
            // 注意要想接住雨水，需要左右都比当前位置高，所以首尾位置处接的水一定是 0。
            if (leftMax < rightMax) {
                // 左边高度小于右边，计算左边的雨水量：左边的最大高度-当前左指针对应的高度，一定要先更新最大高度。
                ans += leftMax - height[left];
                ++left; // 左指针右移
            } else {
                // 右边高度小于等于左边，计算右边的雨水量
                ans += rightMax - height[right];
                --right; // 右指针左移
            }
        }

        return ans; // 返回接雨水的总量
    }
}

• 时间复杂度：$O(n)$，其中 $n$ 是数组 height 的长度。两个指针的移动总次数不超过 n。
• 空间复杂度：$O(1)$。只需要使用常数的额外空间。