解題筆記：運用 Union-Find 巧妙解決「避免洪水」問題

***此篇文章由 Gemini AI 產生*** 在解決演算法問題時，我們時常會發現一些經典的資料結構能夠以意想不到的方式被應用。今天，我想分享一個 LeetCode 上的問題「[Avoid Flood in The City](https://leetcode.com/problems/avoid-flood-in-the-city/)」，以及一個利用 Union-Find (併查集) 資料結構的巧妙解法。 這個解法的第一眼可能讓人覺得有點困惑，但理解其核心思想後，便會讚嘆於其簡潔與高效。 #### **問題簡述** 我們得到一個整數陣列 `rains`，代表每日的天氣狀況。 * `rains[i] > 0`：表示第 `i` 天，`rains[i]` 號湖泊會下雨並且被裝滿。 * `rains[i] == 0`：表示第 `i` 天是晴天，你可以選擇**一個**滿的湖泊將其抽乾。 如果某個湖泊在已經滿了的情況下再次下雨，就會導致洪水。你的任務是回傳一個陣列 `ans`，記錄你在每個晴天抽乾了哪個湖泊，以成功避免所有洪水。如果無法避免，則回傳空陣列。 #### **核心挑戰** 這個問題的挑戰在於「決策」。當你有好幾個晴天和好幾個滿的湖泊時，你應該在哪个晴天抽乾哪個湖泊？ 一個直觀的貪婪策略是：當一個湖泊即將第二次下雨時，我們必須回頭找一個在「上一次下雨」和「這一次下雨」之間的一個晴天，把它抽乾。為了盡可能保留後面的晴天給未來的緊急情況使用，我們應該選擇**最早的那個可用晴天**。 問題來了：如何高效地「找到上一次下雨之後，最早的那個可用晴天」？如果每次都線性掃描，效率會很差。這就是 Union-Find 登場的時機。 #### **Union-Find 的變形與應用** 在這道題目中，Union-Find 的作用不是判斷連通性，而是作為一個「可用晴天」的查找器。它能以近乎 O(1) 的效率告訴我們：「從第 `x` 天開始，下一個可用的晴天是哪一天？」 讓我們看看程式碼的實現： ```cpp class UnionFind { public: vector root; UnionFind(int n) : root(n + 1) { // 初始化，每個節點的根都是它自己 // root = {0, 1, 2, 3, ..., n} iota(root.begin(), root.end(), 0); } // 查找 x 的最終根，帶路徑壓縮優化 int Find(int x) { return (x == root[x]) ? x : root[x] = Find(root[x]); } // 將 x 合併到 x+1 的集合中，表示 x 已被使用 void UnionNext(int x) { root[x] = Find(x + 1); } }; ``` * **初始化**：`root[i] = i`，代表第 `i` 天的「下一個可用日」就是它自己。 * **Find(x)**：查找 `x` 的根。由於路徑壓縮，這會非常快。 * **UnionNext(x)**：這是精髓。當第 `x` 天被「使用」（無論是下雨，還是被安排抽水），我們就執行 `UnionNext(x)`。這會將 `root[x]` 指向 `x+1` 的根。它的效果就像在第 `x` 天立了一個牌子，上面寫著：「此路不通，請找下一天」。因此，下次再執行 `Find(x)` 時，它會自動跳過 `x`，去尋找 `x` 之後第一個可用的日子。 #### **演算法主體邏輯** 有了這個特製的 Union-Find 工具，主體的邏輯就變得清晰了。 ```cpp class Solution { public: vector<int> avoidFlood(vector<int>& rains) { const int n = rains.size(); UnionFind G(n); // 管理 0 到 n-1 天的可用性 unordered_map<int, int> rainDay; // 記錄湖泊最後的下雨日 vector<int> ans(n, 1); // 預設晴天都抽乾 1 號湖 for (int i = 0; i < n; i++) { const int lake = rains[i]; if (lake > 0) { // 如果是雨天 ans[i] = -1; // 雨天答案固定為 -1 // 無論如何，今天下雨了，所以今天也被使用了 G.UnionNext(i); // 檢查這個湖泊之前是否下過雨 auto it = rainDay.find(lake); if (it != rainDay.end()) { // 之前下過雨，必須找個晴天來抽水 int prev = it->second; // 上次下雨日 // 核心：從 prev+1 開始，找最早的可用晴天 int dry = G.Find(prev + 1); if (dry > i) { // 如果找到的晴天在今天之後，來不及了 return {}; // 洪水 } ans[dry] = lake; // 安排在 dry 這天抽乾 lake G.UnionNext(dry); // dry 這天也被使用了 it->second = i; // 更新 lake 的最後下雨日 } else { // 第一次下雨，記錄下來即可 rainDay[lake] = i; } } } return ans; } }; ``` 整個演算法的流程可以總結如下： 1. 遍歷每一天。 2. 如果是**雨天** (`lake > 0`)： * 首先檢查 `rainDay` map，看這個湖之前是否滿了。 * 如果是，就從上一次下雨的後一天 `prev + 1` 開始，呼叫 `G.Find(prev + 1)`。這會高效地返回我們需要的、最早的那個可用晴天。 * 如果返回的晴天 `dry` 比今天 `i` 還晚，表示沒有可用的晴天，洪水無法避免。 * 否則，我們就在 `ans[dry]` 記錄下抽乾 `lake` 的計畫，並用 `G.UnionNext(dry)` 將 `dry` 這天標記為已使用。 * 最後，更新 `rainDay` 中 `lake` 的紀錄，並將今天 `i` 也標記為已使用。 3. 如果是**晴天** (`lake == 0`)： * 我們在迴圈中不做任何事。晴天是一個被動的資源，只有在雨天需要時，才會被 `G.Find()` 找到並分配任務。如果一個晴天沒被用到，它就保留預設值 `ans[i] = 1`。 #### **結論** 這個解法最漂亮的地方在於它將「查找下一個可用空位」這個問題，抽象化為 Union-Find 資料結構的操作。通過 `UnionNext(x)` 將已使用的日期「跳過」，`Find(x)` 就能始終高效地定位到下一個可用的資源。 它是一個很好的例子，展示了如何將一個我們熟悉的資料結構進行微小的改造，來解決一個看似不相關、但本質相通的問題。