LeetCode 筆記 - 1488. Avoid Flood in The City

Posted on

題目在此 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution:
    def avoidFlood(self, rains: list[int]) -> list[int]:
        n = len(rains)
        ans = [1] * n  # 預設晴天都抽乾湖泊1
        full_lakes = {}  # key: lake_id, value: last rain day index
        dry_day_indices = [] # list of indices where rains[i] == 0

        for i, lake in enumerate(rains):
            if lake == 0:
                # 遇到晴天，記錄下這個機會
                dry_day_indices.append(i)
            else:
                # 遇到下雨天，不能抽水
                ans[i] = -1
                
                if lake in full_lakes:
                    # 這個湖泊之前就滿了，需要找一個晴天來排水
                    last_rain_day = full_lakes[lake]
                    
                    # 在晴天列表中，尋找一個在 last_rain_day 之後的最早的晴天
                    # bisect_right 找到插入點，確保是嚴格大於 last_rain_day
                    # it = bisect.bisect_right(dry_day_indices, last_rain_day)

                    it = None
                    left = 0
                    right = len(dry_day_indices) - 1
                    while left <= right:
                        mid = left + (right - left) // 2

                        if dry_day_indices[mid] <= last_rain_day:
                            left = mid + 1
                        else:
                            right = mid - 1
                    it = left

                    # print(dry_day_indices, it)

                    if it == len(dry_day_indices):
                        # 找不到這樣的晴天，洪水無法避免
                        return []
                    
                    # 找到了，就用這個晴天來排水
                    dry_day_to_use_idx = dry_day_indices[it]
                    ans[dry_day_to_use_idx] = lake
                    
                    # 這個晴天已經被用掉了，從列表中移除
                    dry_day_indices.pop(it)

                # 更新這個湖泊的最後下雨日
                full_lakes[lake] = i
                
        return ans

也許你也會想看看