Java怎么解决接雨水问题

# Java怎么解决接雨水问题

## 问题描述

接雨水问题（Trapping Rain Water）是LeetCode上经典的算法题目，题目描述如下：

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

示例：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：可以接住6个单位的雨水（蓝色部分）

## 解决思路

### 1. 暴力解法（按列计算）

对于每一列，找出其左边最高的柱子和右边最高的柱子，取两者较小值减去当前列高度：
```java
public int trap(int[] height) {
    int res = 0;
    for (int i = 1; i < height.length - 1; i++) {
        int leftMax = 0, rightMax = 0;
        // 找左边最高
        for (int j = 0; j < i; j++) {
            leftMax = Math.max(leftMax, height[j]);
        }
        // 找右边最高
        for (int j = i + 1; j < height.length; j++) {
            rightMax = Math.max(rightMax, height[j]);
        }
        // 计算当前列可接雨水
        int min = Math.min(leftMax, rightMax);
        if (min > height[i]) {
            res += min - height[i];
        }
    }
    return res;
}

时间复杂度：O(n²)
空间复杂度：O(1)

2. 动态规划优化

预先存储每个位置的左右最大值，避免重复计算：

public int trap(int[] height) {
    if (height == null || height.length == 0) return 0;
    int n = height.length;
    int[] leftMax = new int[n];
    int[] rightMax = new int[n];
    
    // 初始化左最大值数组
    leftMax[0] = height[0];
    for (int i = 1; i < n; i++) {
        leftMax[i] = Math.max(leftMax[i-1], height[i]);
    }
    
    // 初始化右最大值数组
    rightMax[n-1] = height[n-1];
    for (int i = n-2; i >= 0; i--) {
        rightMax[i] = Math.max(rightMax[i+1], height[i]);
    }
    
    // 计算结果
    int res = 0;
    for (int i = 0; i < n; i++) {
        res += Math.min(leftMax[i], rightMax[i]) - height[i];
    }
    return res;
}

时间复杂度：O(n)
空间复杂度：O(n)

3. 双指针最优解

使用左右指针边走边计算，节省空间：

public int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0;
    int res = 0;
    
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                res += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                res += rightMax - height[right];
            }
            right--;
        }
    }
    return res;
}

时间复杂度：O(n)
空间复杂度：O(1)

算法比较

总结

接雨水问题通过三种不同解法展示了算法优化的典型过程。在实际面试中，建议优先实现双指针解法，其兼具最优时间复杂度和空间复杂度。理解该问题的核心在于分析每个柱子能接多少雨水取决于其左右最高柱子的较小值。 “`