https://youtu.be/91E_W8JhSjs
42. Trapping Rain Water
給定 n 個非負整數表示海拔圖，其中每個條形的寬度為 1，
計算下雨後它可以捕獲多少水。
https://assets.leetcode.com/uploads/2018/10/22/rainwatertrap.png
Topics: Array, Two Pointers, Dynamic Programming, Stack, Monotonic Stack
簡單版解法 就是每個點都找到各自的 左邊最高峰值 跟 右邊最高峰值 就好
剩下就水到渠成 每個點只要比各自的左右峰值低 就能儲水
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
maxLeft, maxRight = [0] * n, [0] * n
for i in range(1, n):
maxLeft[i] = max(height[i-1], maxLeft[i-1])
for i in range(n-2, -1, -1):
maxRight[i] = max(height[i+1], maxRight[i+1])
ans = 0
for i in range(n):
waterLevel = min(maxLeft[i], maxRight[i])
if waterLevel >= height[i]:
ans += waterLevel - height[i]
return ans
難點在於 space O(1) 吧 就不能每個點建立 maxLeft array 跟 maxRight array
而是只能用一個 maxLeft 和 maxRight int 當變數
這裡用 two pointers
左指標跟右指標
然後考慮到maxLeft和maxRight的高低來決定誰是critical factor (水往低處流)
再去決定要計算移動 左指標和maxLeft 還是 右指標和maxRight
class Solution:
def trap(self, height: List[int]) -> int:
if len(height) <= 2: return 0
n = len(height)
maxLeft, maxRight = height[0], height[n-1]
left, right = 1, n - 2
ans = 0
while left <= right:
if maxLeft < maxRight:
if height[left] > maxLeft:
maxLeft = height[left]
else:
ans += maxLeft - height[left]
left += 1
else:
if height[right] > maxRight:
maxRight = height[right]
else:
ans += maxRight - height[right]
right -= 1
return ans
這題HARD的難點大概在於進階解法 這要我自己想大概會想到睡著:(
然後stack的解法我也懶得讀了 這交給以後的我解決就好