題目敘述
題目會給我們一個陣列，陣列裡面每個數字分別代表高低各不同的隔板高度，問我們從降雨之後，最多可以儲存多少水量?測試範例
Example 1:
範例一的圖解
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
藍色部分的方格，代表可以儲存雨水的格子點。
Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9
約束條件
Constraints:
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
演算法
其實這一題和前面學過的水槽模型裝水那一題九成像。
都是給我們隔板高度，要求我們計算最多可以儲存的水量是多少?
差別在於:
前一題的水槽底部是平的。
這一題的水槽底部高低不同，有凹有凸。
但是，最關鍵的核心精神相同，可以裝的水量多寡由比較矮的隔板決定。
(因為水只要超過比較矮的那一邊就會溢出去，就算再下雨注入水也
無法儲存更多了。)
因此，我們只要建立一個滑窗，每次在水平方向移動一格，收縮比較矮的一邊，
如果左邊的隔板比右邊矮，就收縮左邊。
如果右邊的隔板比左邊矮，就收縮右邊。
每次迭代的時候，同步更新累加
當下可以儲存的水量 = 比較矮的隔板高度 - 水槽底部高度
(相當於二維平面上投影的面積，就像範例圖中的樣子)
最後，回傳能儲存雨水的總面積，就是答案。
程式碼
class Solution:
def trap(self, height: List[int]) -> int:
if len(height) < 3:
# Quick response for impossible cases
return 0
volume, size = 0, len(height)
# two pointers, initialized as boundary index
left, right = 0, size-1
# local max height on two sides
left_wall_max, right_wall_max = height[left], height[right]
# scan each index with two-pointers
while left < right:
# update local max height
left_wall_max, right_wall_max = max(height[left], left_wall_max), max(height[right], right_wall_max)
if left_wall_max <= right_wall_max:
# left wall is shorter than right wall
# update trapping rain water of current index
volume += left_wall_max - height[left]
# move left pointer to right hand side
left += 1
else:
# right wall is shorter than left wall
# update trapping rain water of current index
volume += right_wall_max - height[right]
# move right pointer to left hand side
right -= 1
return volume
複雜度分析
時間複雜度:
O( n ) 收縮滑窗，滑窗寬度從n-1 收縮到 1，總共耗費O(n)的時間
空間複雜度:
O(1) 都是臨時變數，所占用的記憶體空間固定，都是常數級別O(1)
關鍵知識點
這一題用到的也是水槽裝水的模型，唯一的小差別就是多了水槽底部有了高度，但是核心精神不變: 可以裝的水量多寡由比較矮的隔板決定。
強烈建議複習Container With Most Water這一題，
鞏固 水槽裝水的模型 與 雙指針應用的知識點
Reference:
[1] Python O(n) by two-pointers // DP [w/ Hint] - Trapping Rain Water - LeetCode
