LC42：接雨水

题目描述

给定 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

分析

我们可以按列分析，即考虑每列的柱子上能“顶着”多少雨水。对于第 i 列，想要求出其能接多少雨水，我们需要分别求出左右两侧最高的柱子 max_left 和 max_right，根据木桶原理，第 i 列能“顶”的水量为 min(max_left, max_right) - height[i]。于是，问题就演变成求每一列的 max_left 和 max_right。

我们可以使用动态规划求解。dp_left[i] 表示第 i 列左侧柱子的最大值，dp_right[i] 表示右侧柱子的最大值。转移方程为：

dp_left[i] = max(dp_left[i - 1], height[i])
dp_right[i] = max(dp_right[i + 1], height[i])

这里其实省略了一步，dp_left[i] 应该等于 max(dp_left[i - 2], height[i - 1])，即计算每一列左侧的最大值且不包括该列本身。但是为什么我们可以让该列本身的值也参与计算呢？因为其实本列高度不影响结果：

• 如果 height[i] <= height[i - 1]，则两种计算方法结果一致；
• 如果 height[i] > height[i - 1]，则本身这列接的水量就是 0，也没有影响。反而是用 max(dp_left[i - 2], height[i - 1]) 会造成实现上的繁琐，因此我们直接采用简单的方法计算。

我们只需算出 dp 数组，再遍历一遍即可得到答案，时间复杂度为 O(n)，空间复杂度为 O(n)。

我们可以用双指针法来优化空间复杂度。

由于每个 max_left 和 max_right 只使用了一次，因此我们不需要使用 dp 数组保存全部的 max_left 和 max_right，只需要在遍历的过程中动态更新即可。如果是从左往右遍历的话，对于 max_left，可以通过 max(max_left, height[i]) 简单地计算，而 max_right 则需要每次扫描右边的所有值才能得到，因此我们引入了双指针 left 和 right 从两侧向中间进行双向遍历。

如何确定每次移动 left 还是 right 指针呢？假设某一位置 max_left < max_right，则不管右边的 right 指针如何移动，left 位置的水量由 max_left 和右边的某个更大的值中的较小值决定。而由于 max_left < max_right，min(max_left, 更高的 max_right) 仍然是 max_left。因此，此时可以确定 left 位置的水量为 max_left - height[left]，然后移动左指针。

因此，当 max_left 较小时处理左指针，反之处理右指针。

双指针法时间复杂度为 O(n)，空间复杂度为 O(1)。

实现

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int maxleft = 0, maxright = 0;
        int ans = 0;
        while (right >= left) {
            maxleft = Math.max(maxleft, height[left]);
            maxright = Math.max(maxright, height[right]);
            if (maxleft > maxright) {
                ans += maxright - height[right];
                right--;
            } else {
                ans += maxleft - height[left];
                left++;
            }
        }
        return ans;
    }
}