如何使用Java解决接雨水问题

引言

接雨水问题（Rain Water Trapping Problem）是一个经典的算法问题，通常用于考察对数组和双指针等基本数据结构的理解。该问题的描述如下：给定一个非负整数数组，表示一个高度图，计算这个高度图能够接住多少雨水。

问题描述

给定一个非负整数数组 height，其中每个元素表示一个柱子的高度。假设这些柱子之间的宽度为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个单位的雨水（蓝色部分）。

解决思路

1. 暴力法

最直观的解决方法是对于每个柱子，找到其左边和右边的最高柱子，然后计算当前柱子能够接住的雨水量。具体步骤如下：

1. 遍历数组中的每个元素。
2. 对于当前元素，找到其左边最高的柱子 left_max 和右边最高的柱子 right_max。
3. 当前柱子能够接住的雨水量为 min(left_max, right_max) - height[i]。
4. 将所有柱子能够接住的雨水量累加。

代码实现

public int trap(int[] height) {
    int totalWater = 0;
    for (int i = 1; i < height.length - 1; i++) {
        int leftMax = 0, rightMax = 0;
        for (int j = i; j >= 0; j--) {
            leftMax = Math.max(leftMax, height[j]);
        }
        for (int j = i; j < height.length; j++) {
            rightMax = Math.max(rightMax, height[j]);
        }
        totalWater += Math.min(leftMax, rightMax) - height[i];
    }
    return totalWater;
}

复杂度分析

• 时间复杂度：O(n^2)，对于每个元素，都需要遍历整个数组来找到左边和右边的最高柱子。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

2. 双指针法

为了提高效率，可以使用双指针法来优化暴力法。双指针法的核心思想是通过两个指针分别从数组的两端向中间移动，同时维护两个变量 left_max 和 right_max 来记录左边和右边的最高柱子。

代码实现

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

复杂度分析

• 时间复杂度：O(n)，只需要遍历数组一次。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

3. 动态规划法

动态规划法通过预先计算每个位置的左边最高柱子和右边最高柱子，从而避免在每次计算时重复遍历数组。

代码实现

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 totalWater = 0;
    for (int i = 0; i < n; i++) {
        totalWater += Math.min(leftMax[i], rightMax[i]) - height[i];
    }
    return totalWater;
}

复杂度分析

• 时间复杂度：O(n)，需要遍历数组三次。
• 空间复杂度：O(n)，需要额外的数组来存储左边和右边的最高柱子。

结论

接雨水问题可以通过多种方法解决，其中双指针法和动态规划法是最常用的高效解决方案。双指针法在时间复杂度上最优，而动态规划法则在空间复杂度上稍逊一筹。根据实际需求选择合适的算法可以有效提高程序的性能。

通过本文的介绍，相信读者已经掌握了如何使用Java解决接雨水问题。希望这些方法能够帮助你在实际编程中更好地应对类似的问题。