LeetCode 42 接雨水：动态规划、单调栈与双指针解法（Java）

一、引言

LeetCode 42 接雨水是数组类算法题的经典代表，也是面试中的高频考点。这道题的核心是理解'每个位置接雨水量由左右最大高度决定'，而动态规划、单调栈、双指针则是解决该问题的三大核心思路。

二、动态规划

2.1 解题步骤

朴素的做法是对于数组 height 中的每个元素，分别向左和向右扫描并记录左边和右边的最大高度，然后计算每个下标位置能接的雨水量。

我们可以清晰地看出可以接水的格子是左边最高和右边最高都高于自己本身的高度，也就是凹下去，才能成功接水。而接水的高度则是左边右边最高中较矮的一侧减去自己本身。

所以我们的解题步骤是：

• 先计算出当前柱子左边最高的柱子和右边最高的柱子
• *当前柱子接水面积 = （min(左高，右高) - 自身高度）1
• 将面积累加。

2.2 动态规划的使用

但是我们每次计算柱子的左高和右高都去遍历一次数组其实时间复杂度会达到 O(n^2)，所以我们可以使用动态规划。

动态规划（Dynamic Programming，简称 DP）核心是把复杂问题拆解成多个可重复解决的子问题，并把子问题的答案保存下来（避免重复计算），最终通过子问题的解推导出原问题的解。

• 我们把计算接水总面积拆分成计算单个柱子的接水面积
• 并且记录下单个柱子的左高和右高，方便计算下一个柱子的左高和右高
• 最后再把单个柱子的面积累加

2.3 代码实现

/**
 * 动态规划
 * @param height 柱子的高度
 * @return 接住雨水的总数
 */
public int trap(int[] height) {
    int len = height.length;
    // 当柱子个数小于三时，无法接到雨水
    // 接雨水的条件是两边的比中间高，所以至少要有三个柱子
    if (len < 3) {
        return 0;
    }
    //记录第 i 根柱子左边（包括自身）中最高柱子的高度
    int[] leftMax = new int[len];
    leftMax[0] = height[0];
    for (int i = 1; i < len; ++i) {
        //复用上一根柱子的左高，优化了时间复杂度
        leftMax[i] = Math.max(leftMax[i - 1], height[i]);
    }
    
    [] rightMax =  [len];
    rightMax[len - ] = height[len - ];
     (   len - ; i >= ; --i) {
        rightMax[i] = Math.max(rightMax[i + ], height[i]);
    }
    
       ;
     (   ; i < len; ++i) {
        
        ans += Math.min(leftMax[i], rightMax[i]) - height[i];
    }
     ans;
}