leetcode-42.接雨水

dp

使用动态规划的方法来解决“接雨水”问题也是一种有效的策略。动态规划的基本思想是预先计算出每个位置的左侧和右侧的最大高度，然后根据这些预计算的结果来确定每个位置可以存储的雨水量。

动态规划方法

算法步骤

1. 初始化：

   • 创建两个数组 leftMax 和 rightMax，用于存储每个位置左侧和右侧的最大高度。
   • 初始化 water 为 0，用于存储总的雨水量。

2. 计算左侧最大高度：

   • 从左到右遍历高度数组，填充 leftMax 数组。
   • 对于每个位置 i，leftMax[i] 是 height[0] 到 height[i] 的最大值。

3. 计算右侧最大高度：

   • 从右到左遍历高度数组，填充 rightMax 数组。
   • 对于每个位置 i，rightMax[i] 是 height[i] 到 height[n-1] 的最大值。

4. 计算雨水量：

   • 遍历每个位置，计算当前位置能接的雨水量为 min(leftMax[i], rightMax[i]) - height[i]。
   • 将每个位置的雨水量累加到 water。

5. 返回结果：

   • 返回 water，即总的雨水量。

Java 实现

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int len = height.length;
        int[] dpLeft = new int[len];
        int[] dpRight = new int[len];
        // init
        dpLeft[0] = height[0];
        dpRight[len - 1] = height[len - 1];
        // core
        for (int i = 1; i < len; i++) {
            dpLeft[i] = Math.max(dpLeft[i - 1], height[i]);
        }
        for (int i = len - 2; i >= 0; i--) {
            dpRight[i] = Math.max(dpRight[i + 1], height[i]);
        }
        for (int i = 0; i < len; i++) {
            ans += Math.min(dpLeft[i], dpRight[i]) - height[i];
        }
        return ans;
    }
}

代码说明

• 左侧最大高度数组 leftMax：用于存储每个位置左侧的最大柱子高度。
• 右侧最大高度数组 rightMax：用于存储每个位置右侧的最大柱子高度。
• 雨水计算：对于每个位置，雨水量是 min(leftMax[i], rightMax[i]) - height[i]，即当前位置能存储的水量。

这种方法的时间复杂度为 O(n)，空间复杂度为 O(n)，因为需要额外的两个数组来存储左侧和右侧的最大高度。