LeetCode 筆記 - 1488. Avoid Flood in The City
題目在此 1488. Avoid Flood in The City
給定一個整數陣列 rains,其中 rains[i] > 0 表示第 i 天下雨,且 rains[i] 是下雨的湖泊編號;rains[i] == 0 表示第 i 天沒有下雨,可以選擇乾旱一個湖泊。
請你返回一個陣列 result,其中 result[i] == -1 表示第 i 天下雨,result[i] 是乾旱的湖泊編號。若無法避免洪水,請返回空陣列。
解題思維
這題的關鍵在於追蹤每個湖泊的狀態,並在晴天時選擇適當的湖泊進行乾旱,以避免洪水。
我們可以使用一個字典 full_lakes 來記錄每個湖泊哪一天最後一次下雨,並使用一個列表 dry_day_indices 來記錄所有晴天的索引。
當我們遇到下雨天時,我們檢查該湖泊是否已經滿了(即是否在 full_lakes 中)。如果滿了,我們需要在 dry_day_indices 中找到一個晴天來乾旱這個湖泊。如果找不到合適的晴天,則無法避免洪水,返回空陣列。
所以問題的關鍵是如何快速的在 dry_day_indices 中找到一個大於 last_rain_day 的晴天索引。
在這裡,可以用二分搜尋來達成這個目標。
Time complexity 是 $O(N \log N)$,其中 N 是 rains 的長度。每次遇到下雨天時,我們可能需要在 dry_day_indices 中進行一次二分搜尋,這需要 $O(\log N)$ 的時間。
Space complexity 是 $O(N)$,因為我們需要存儲 full_lakes 和 dry_day_indices。
程式碼
1 | class Solution: |