LeetCode 42. 接雨水 [Hot 100] —— DP/双指针

42. 接雨水

已解答

算术评级: 6

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

第一种解法：动态规划（双数组法）

核心思路：

1. 分别计算每个位置左侧的最大高度（left 数组）和右侧的最大高度（right 数组）
2. 对于每个位置，能接的雨水量取决于左右两侧最大高度中的较小值与当前位置高度的差值

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] left = new int[n];
        int[] right = new int[n];
        for (int i = 0; i < n; i++) {
            if (i>0) left[i] = Math.max(left[i-1],height[i]);
            else left[i] = height[i];
        }
        for (int i = n-1; i >= 0; i--) {
            if (i<n-1) right[i] = Math.max(right[i+1], height[i]);
            else right[i] = height[i];
        }
        int ans = 0;
        for (int i = 1; i < n-1; i++) {
            int h = Math.min(left[i-1], right[i+1]);
            ans += h - height[i];
        }
        // 或者
        // for (int i = 1; i < n-1; i++) {
        //     int h = Math.min(left[i], right[i]);
        //     ans += h;
        // }
        return ans;
    }
}

第二种解法：双指针法

核心思路：

1. 使用左右两个指针从两端向中间移动
2. 维护两个变量 preMax 和 nextMax，分别记录左侧和右侧已遍历的最大高度
3. 根据当前左右最大值的大小决定移动哪个指针，并计算当前位置能接的雨水量

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int l = 0;
        int r = n - 1;
        int ans = 0;
        int preMax = 0;
        int nextMax = 0;
        while (l < r) {
            preMax = Math.max(preMax, height[l]);
            nextMax = Math.max(nextMax, height[r]);
            if (preMax < nextMax) {
                ans += preMax - height[l];
                l++;
            } else {
                ans += nextMax - height[r];
                r--;
            }
        }
        return ans;
    }
}