如何使用java解決接雨水問題

如何使用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解決接雨水問題。希望這些方法能夠幫助你在實際編程中更好地應對類似的問題。