[BGD ] 私は雨

看板Marginalman作者cities516 (守岸人的調律者)時間1年前 (2024/11/27 02:45)推噓1(1推 0噓 3→)

留言4則, 4人參與討論串1/1

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的解法我也懶得讀了這交給以後的我解決就好 -- https://i.imgur.com/Woyioru.gif