題目連結(https://leetcode.com/problems/avoid-flood-in-the-city/description/?envType=daily-question&envId=2025-10-07)

Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over the nth lake, the nth lake becomes full of water. If it rains over a lake that is full of water, there will be a flood. Your goal is to avoid floods in any lake.

Given an integer array rains where:

• rains[i] > 0 means there will be rains over the rains[i] lake.
• rains[i] == 0 means there are no rains this day and you can choose one lake this day and dry it.

Return an array ans where:

• ans.length == rains.length
• ans[i] == -1 if rains[i] > 0.
• ans[i] is the lake you choose to dry in the ith day if rains[i] == 0.

If there are multiple valid answers return any of them. If it is impossible to avoid flood return an empty array.

Notice that if you chose to dry a full lake, it becomes empty, but if you chose to dry an empty lake, nothing changes.

二分搜尋之進階題

1. Repeat（題目重複確認）

• 輸入：integer array rains , 陣列中的數如果等於 0 代表沒有下雨，如果大於 0 代表在第 N 個湖下雨，雨下在已經滿了的湖會造成洪水，要避免洪水發生
• 輸出：回傳一個 array ans , 陣列中的值==-1 表示當天有下雨，==0 表示當天沒下雨，因此可以選擇一個湖去放乾它
• 前提：
  • 1 <= rains.length <= 10^5
  • 0 <= rains[i] <= 10^9 陣列規模很大

2. Examples（舉例確認理解）

Input: rains = [1,2,0,0,2,1]
Output: [-1,-1,2,1,-1,-1]
Explanation: After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day, we dry lake 2. Full lakes are [1]
After the fourth day, we dry lake 1. There is no full lakes.
After the fifth day, full lakes are [2].
After the sixth day, full lakes are [1,2].
It is easy that this scenario is flood-free. [-1,-1,1,2,-1,-1] is another acceptable scenario.

Input: rains = [1,2,3,4]
Output: [-1,-1,-1,-1]
Explanation: After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day full lakes are [1,2,3]
After the fourth day full lakes are [1,2,3,4]
There's no day to dry any lake and there is no flood in any lake.

3. Approach（解題思路）

方法 ：二分搜尋

• 使用兩個結構：
  • lastrain：記錄每個湖泊最後一次下雨的日期。
  • drydays：一個集合，用來存儲晴天的日期索引，這些日子我們可以用來乾燥湖泊。
• 策略：
  • 若當天下雨：
    • 將該湖泊的最後一次下雨日期更新。
    • 若該湖泊之前已經下過雨，則需要從 drydays 中選擇一個適合的晴天進行乾燥操作，避免洪水。兩次下雨之間找到一個晴天
  • 若當天沒有下雨：
    • 將當天的日期加入 drydays 集合，這是我們將來可以乾燥湖泊的可用日子。
• 重點：
  • 利用二分搜尋的方式來高效查找可乾燥的日期（upper_bound）。
  • 若無法找到合適的乾燥日期，則返回空陣列，表示無法避免洪水。
• 時間複雜度：O(n) 其中 n 是 rains 的長度，遍歷一次 rains 並且對每一天進行處理。使用 unordered_map 和 set 來記錄並查找數據，它們的平均操作時間是 O(1) 和 O(log n)。
• 空間複雜度：O(n)

4. Code（C++）

class Solution {
public:
    vector<int> avoidFlood(vector<int>& rains) {
        int n = rains.size();
        vector<int> ans(n);
        
        unordered_map<int, int> lastrain;  // lake -> 上次下雨日
        set<int> drydays;                  // 可用的晴天索引
        
        for (int i = 0; i < n; i++) {
            if (rains[i] == 0) {
                // 晴天：先記錄，稍後決定抽哪個湖
                drydays.insert(i);
                ans[i] = 1;  // 預設值（如果沒有湖需要抽）
            } 
            else {
                // 下雨天
                int lake = rains[i];
                ans[i] = -1;
                
                if (lastrain.count(lake)) {
                    // 湖已滿！必須在上次下雨和這次下雨之間找晴天抽它
                    int prevrainday = lastrain[lake];
                    auto it = drydays.upper_bound(prevrainday);
                    
                    if (it == drydays.end()) {
                        // 找不到合適的晴天 → 洪水無法避免
                        return {};
                    }
                    
                    // 用這個晴天抽水
                    ans[*it] = lake;
                    drydays.erase(it);
              }
                
                // 更新這個湖的最後下雨日
                lastrain[lake] = i;
            }
        }
        
        return ans;
    }
};

5. Test 範例

rains = [1, 2, 0, 0, 2, 1]

Day 0: 下雨湖1
  lastRain = {1:0}
  dryDays = {}
  ans = [-1, _, _, _, _, _]

Day 1: 下雨湖2
  lastRain = {1:0, 2:1}
  dryDays = {}
  ans = [-1, -1, _, _, _, _]

Day 2: 晴天
  dryDays = {2}
  ans = [-1, -1, 1, _, _, _]  (預設1)

Day 3: 晴天
  dryDays = {2, 3}
  ans = [-1, -1, 1, 1, _, _]

Day 4: 下雨湖2 (重複！)
  lastRain[2] = 1 存在
  找 upper_bound(1) in {2,3} → 2
  ans[2] = 2
  dryDays = {3}
  lastRain = {1:0, 2:4}
  ans = [-1, -1, 2, 1, -1, _]

Day 5: 下雨湖1 (重複！)
  lastRain[1] = 0 存在
  找 upper_bound(0) in {3} → 3
  ans[3] = 1
  dryDays = {}
  lastRain = {1:5, 2:4}
  ans = [-1, -1, 2, 1, -1, -1]

結果: [-1, -1, 2, 1, -1, -1] ✓

6. 相關題目與延伸概念

• 優化二分搜尋：如何有效地利用 set 中的 upper_bound 方法來查找可用的乾燥日期。
• 紅黑樹：在這題中，set 使用的底層結構是紅黑樹，它可以在 O(log n) 時間內完成查找和插入操作，這對於解決大規模問題非常有用。
• 類似題目：
  • LeetCode 981: Time Based Key-Value Store
  • LeetCode 368: Largest Divisible Subset

7. 補充：語法＆注意事項

• 邊界條件：某些測試案例可能有特殊情況
• 預設值處理：晴天如果沒被使用，ans[i] = 1 是任意值即可

ps. 部分內容經 AI 協助整理