🔗 🟡 1488. Avoid Flood in The City

Problem Statement

題目簡述

給定一個長度為 nn 的整數陣列 rains，其中：

  • rains[i] > 0 表示第 ii 天在湖泊 rains[i] 下雨。如果此時該湖泊已經是滿的，就會發生洪水。
  • rains[i] == 0 表示第 ii 天是晴天，你可以選擇任意一個滿的湖泊將其抽乾（使其變為空）。

請回傳一個長度為 nn 的答案陣列 ans：

  • 若第 ii 天下雨，ans[i] = -1。
  • 若第 ii 天是晴天，ans[i] 為你選擇抽乾的湖泊編號（若沒有湖泊需要抽乾，可填入任意正整數如 1）。
  • 若無法避免洪水，回傳空陣列 []。

Constraints

約束條件

  • 1≤rains.length≤1051 \le \text{rains.length} \le 10^5
  • 0≤rains[i]≤1090 \le \text{rains}[i] \le 10^9

思路：貪心策略與可用時間維護

本題訓練目標

本題是一道非常經典的 貪心 + 有序集合二分 或 區間併查集 題目。核心在於如何合理分配「晴天」這項寶貴資源，來化解未來可能發生的洪水危機。

核心貪心策略

假設某個湖泊在第 t1t_1 天下雨，接著在更晚的第 t2t_2 天再次下雨。為了防止這個湖泊溢出，我們必須在區間 (t1,t2)(t_1, t_2) 之間的某個晴天，將該湖泊抽乾。

如果這段區間內有多個晴天，我們應該選擇哪一個？

  • 貪心原則：我們應該選擇大於 t1t_1 的 第一個（最左邊的） 可用晴天。
  • 直覺解釋：越早使用這個晴天資源，對未來的決策越有利。如果我們把這個湖泊的抽水時間往後拖延，可能會佔用到其他更晚下雨、但急需抽乾的湖泊的晴天資源。

方法一：有序容器上二分

根據貪心策略，問題可以轉化為：當我們發現某個湖泊在今天（第 t2t_2 天）再次下雨時，我們需要在所有「尚未被佔用的晴天」中，尋找第一個大於上次下雨天 t1t_1 的晴天。

核心想法是利用雜湊表記錄每個湖泊最後一次下雨的時間，並以有序容器（如 SortedList）動態維護所有還沒被使用的晴天日期。

遍歷每一天，若是晴天則先記錄下來；若某個湖泊再次下雨，我們就去有序容器中二分搜尋第一個大於該湖泊「上次下雨時間」的晴天。如果能找到，就在該晴天抽乾它，並將該晴天從容器中移除；若找不到，說明無法避免洪水，直接回傳空陣列。

可復用模型：有序容器維護可用資源

當我們需要在一堆「動態產生且可被消耗的資源」中，尋找並使用「大於某個門檻值的最小資源」時，有序容器 + 二分搜尋是極為通用的標準模板。

複雜度分析

  • 時間複雜度：O(nlog⁡n)\mathcal{O}(n \log n)。我們需要遍歷長度為 nn 的陣列。每次遇到重複下雨時，在有序容器中二分搜尋並刪除元素需要 O(log⁡n)\mathcal{O}(\log n) 的時間。
  • 空間複雜度：O(n)\mathcal{O}(n)。我們需要雜湊表記錄湖泊的最後下雨日期，以及有序容器儲存晴天的日期，最多佔用 O(n)\mathcal{O}(n) 的空間。

方法二：區間併查集

為了避免二分搜尋的 O(log⁡n)\mathcal{O}(\log n) 開銷，我們可以用區間併查集將尋找晴天的複雜度優化到接近 O(1)\mathcal{O}(1)。

相比於普通的併查集，將合併時改成向右合併，便可以用來維護區間，使得 find(x)\text{find}(x) 表示自第 xx 天起第一個可用於抽水的晴天位置。

當湖泊在上次下雨時間 t1t_1 之後需要被抽乾時，我們可以直接透過 find(t1)\text{find}(t_1) 瞬間定位到最左邊的可用晴天 jj：

  • 若 j≥ij \ge i，說明兩次下雨之間沒有可用的晴天，無法避免洪水。
  • 否則，在第 jj 天抽水，並透過 union(j, j + 1) 將其標記為已使用。此外，今天（下雨天）也不能被其他湖泊佔用，故同樣執行 union(i, i + 1)。
核心觀察：併查集維護連續區間的可用性

併查集的 find 操作具有路徑壓縮的特性。當我們把已使用的位置 jj 指向 j+1j+1 時，後續對該區域的 find 呼叫會自動「跳過」所有已使用的連續區間，瞬間抵達下一個真正的可用空位。這是區間併查集非常高級且優雅的應用。

複雜度分析

  • 時間複雜度：O(n⋅α(n))\mathcal{O}(n \cdot \alpha(n))，其中 α\alpha 是反阿克曼函數，在實際應用中可視為常數。由於併查集帶有路徑壓縮，每次的查詢與合併操作接近 O(1)\mathcal{O}(1)，因此整體時間複雜度為 O(n)\mathcal{O}(n)。
  • 空間複雜度：O(n)\mathcal{O}(n)。需要一個大小為 n+1n+1 的併查集陣列以及雜湊表記錄狀態，空間複雜度為 O(n)\mathcal{O}(n)。

Code

方法一：有序容器上二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        n = len(rains)

        ans = [1] * n
        mp = dict()  # x -> last_rain
        sl = SortedList()  # 有序容器維護可用的位置
        for i, x in enumerate(rains):
            if x == 0:
                sl.add(i)
            else:
                if x in mp:
                    # 需要先清掉積水
                    idx = sl.bisect_right(mp[x])
                    if idx == len(sl):  # 沒有可用的位置
                        return []
                    ans[sl.pop(idx)] = x
                mp[x] = i
                ans[i] = -1
        return ans

方法二：區間併查集

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
class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        n = len(rains)

        ans = [1] * n
        mp = dict()  # x -> last_rain

        # 區間並查集維護可用的位置
        # fa[i] = j 表示從位置 i 開始，下一個可用的位置是 j
        fa = list(range(n + 1))  # 注意要 +1，因為可能會 union(n - 1, n)

        def find(x: int) -> int:
            while x != fa[x]:
                fa[x] = fa[fa[x]]
                x = fa[x]
            return x
            
        def union(x: int, y: int) -> bool:
            fx, fy = find(x), find(y)
            if fx == fy:
                return False
            fa[x] = fy
            return True
        
        for i, x in enumerate(rains):
            if x > 0:
                if x in mp:
                    # 需要先清掉積水
                    j = find(mp[x])
                    if j >= i:
                        return []
                    ans[j] = x
                    union(j, j + 1)  # 將 j 標記為不可用
                mp[x] = i
                ans[i] = -1
                union(i, i + 1)  # 將 i 標記為不可用
        return ans