題目
#

leetcode 42 - Trapping Rain Water (題目說明請點連結)

題目簡述
#

給定一個表示牆壁高度的陣列，計算能夠收集的雨水總量。

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: 上面的高程圖（黑色部分）由陣列 [0,1,0,2,1,0,1,3,2,1,2,1] 表示。在這種情況下，有 6 個單位的雨水（藍色部分）被收集。

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9
Explanation: 有 9 個單位的雨水被收集。

解題思路
#

輸入給定一個牆壁高度的陣列如上圖所示，算出此牆面能累積的總水量。
此題能使用雙向指針的概念，分別紀錄left與right的位置。 Trapping Rain Water

因為水往低處流，分別以maxLeft 與 maxRight 紀錄二側指針由外向內的最高位
置，每走到一個地方就由二側的最高高度-當前高度，即會得該處的蓄水量。

以圖例為例，
當left走到該處:
當前蓄水量為 maxLeft - current，也就是之前紀錄的1 - 當前的高0 = 1
當right走到該處:
當前蓄水量為 maxLeft - current，也就是之前紀錄的2 - 當前的高1 = 1 Trapping Rain Water

最後left與right 相會結束程式，輸出總水量即可

完整程式碼
#

java

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1; // 初始化左右指針
        int maxLeft = height[left], maxRight = height[right]; // 初始化左右兩側的最大高度
        int water = 0; // 初始化總蓄水量

        while(left < right) { // 當左右指針未相遇時繼續
            if(maxLeft < maxRight) { // 如果左側最大高度小於右側
                left++; // 移動左指針
                maxLeft = Math.max(maxLeft, height[left]); // 更新左側最大高度
                water += maxLeft - height[left]; // 計算當前位置的蓄水量
            } else { // 如果右側最大高度小於等於左側
                right--; // 移動右指針
                maxRight = Math.max(maxRight, height[right]); // 更新右側最大高度
                water += maxRight - height[right]; // 計算當前位置的蓄水量
            }
        }
        return water; // 返回總蓄水量
    }
}