題目

代碼

# 接雨水算法
def trap(height):# 1. 特殊情況：數組為空 則返回0if not height:return 0n = len(height)# 2. 初始化左右指針，左右最大值，結果left, right = 0, n - 1# maxleft代表左邊最大值，maxright代表右邊最大值maxleft, maxright = height[0], height[n - 1]# ans代表結果ans = 0# 左右指針相遇時結束while left <= right:# 更新左右最大值maxleft = max(height[left], maxleft)maxright = max(height[right], maxright)# 判斷左右最大值，小的一邊進行計算# 雨滴的高度為左右最大值中的小值減去當前高度if maxleft < maxright:ans += maxleft - height[left]left += 1else:ans += maxright - height[right]right -= 1return ans# 計算數據 height = [0,1,0,2,1,0,1,3,2,1,2,1]
height = [0,1,0,2,1,0,1,3,2,1,2,1]
print(trap(height))  # 6

思路

中文解釋

1. 特殊情況處理：如果輸入的高度數組為空，則返回0。
2. 初始化：定義左右指針left和right，分別指向數組的兩端。定義maxleft和maxright，分別表示左邊和右邊的最大值。定義ans用于存儲結果。
3. 循環計算：當左右指針沒有相遇時，進行以下操作：
   • 更新maxleft和maxright，分別為當前指針位置的高度和之前最大值中的較大者。
   • 比較maxleft和maxright，選擇較小的一邊進行計算：
     • 如果maxleft較小，則計算左邊的雨水高度，并將左指針右移。
     • 否則，計算右邊的雨水高度，并將右指針左移。
4. 返回結果：循環結束后，返回計算得到的雨水總量ans。

圖示

以下是一個示例圖示，展示了算法的工作原理：

高度數組: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]初始狀態:
left -> 0
right -> 11
maxleft -> 0
maxright -> 1
ans -> 0每一步的狀態變化:
1. left -> 1, maxleft -> 1, ans -> 0
2. right -> 10, maxright -> 2, ans -> 0
3. left -> 2, maxleft -> 1, ans -> 1
4. left -> 3, maxleft -> 2, ans -> 1
5. right -> 9, maxright -> 2, ans -> 2
6. right -> 8, maxright -> 2, ans -> 2
7. right -> 7, maxright -> 3, ans -> 2
8. left -> 4, maxleft -> 2, ans -> 2
9. left -> 5, maxleft -> 2, ans -> 4
10. left -> 6, maxleft -> 2, ans -> 5
11. left -> 7, maxleft -> 3, ans -> 6最終結果: 6

通過上述步驟，算法計算出總共可以接住6個單位的雨水。