42. 接雨水

接雨水

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

样例

---

Example

示例 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

思路

---

• 前缀数组：对于每个柱子，上方水的高度取决于它左边最高的柱子和右边最高的柱子的较小侧，因此我们可以通过前缀数组计算出每一个柱子左右的最高柱子，然后用ans += min(leftMax[i], rightMax[i]) - height[i]累加计算结果。为了避免左右最大高度小于自身，所以自己也参加左右最大高度计算。
• 双指针一：使用双指针维护左右从外向里维护左右最大高度，对于较小的一侧所处柱子进行计算，因为该柱子的较小方最大高度是已知的，另一方最大高度虽未知，但一定大于目前的最大高度，因而也大于较小一侧最大高度。

答案

---

Java

// 前缀数组
class Solution {
    public int trap(int[] height) {
        int n = height.length, ans = 0;
        int[] lh = new int[n], rh = new int[n];
        lh[0] = height[0];
        rh[n - 1] = height[n - 1];
        for (int i = 1; i < n; i++) {
            lh[i] = Math.max(lh[i - 1], height[i]);
        }
        for (int i = n - 2; i >= 0; i--) {
            rh[i] = Math.max(rh[i + 1], height[i]);
        }
        for (int i = 0; i < n; i++) {
            ans += Math.min(lh[i], rh[i]) - height[i];
        }
        return ans;
    }
}
 
// 双指针一
class Solution {
    public int trap(int[] height) {
        int n = height.length, l = 0, r = n - 1, ans = 0, lh = height[l], rh = height[r];
        while (l < r) {
            if (lh > rh) {
                ans += rh - height[r];
                r--;
                rh = Math.max(rh, height[r]);
            } else {
                ans += lh - height[l];
                l++;
                lh = Math.max(lh, height[l]);
            }
        }
        return ans;
    }
}