顯示具有 UnionFind 標籤的文章。 顯示所有文章
顯示具有 UnionFind 標籤的文章。 顯示所有文章

2026年3月12日 星期四

從 LeetCode 3600 看工程思維:極致效能 vs 萬用架構

在面對演算法挑戰時,我們常常會陷入「尋求最快解」的迷思。然而,在真實世界的軟體工程中,最快的演算法真的永遠是最好的選擇嗎?

今天我們透過 LeetCode 3600: Maximize Spanning Tree Stability with Upgrades 這道經典的圖論題,來看看兩種截然不同的解題思路,以及它們在現實工業界中各自稱霸的真實場景。

題目背景:尋找最穩定的生成樹

這道題目的核心目標是:在給定的一張圖中,挑選出 $N-1$ 條邊形成「生成樹 (Spanning Tree)」。其中有些邊是「必選的」,有些是「可選的」。我們手上有 $K$ 次升級機會,可以將可選邊的強度乘以 2。 目標:最大化這棵樹的「最弱連結 (最小邊緣強度)」。

面對這個「最大化最小值」的難題,我們有兩種截然不同的解題策略。

策略一:二分搜尋 + 貪心驗證 (Binary Search on Answer)

這是一個非常扎實且通用的工程思維:我們不知道答案是多少,但我們可以「猜」。

運作邏輯:

  1. 確定答案的上下界(例如強度從 $0$ 到 $100,000$)。

  2. 猜測一個目標值 mid,並寫一個 check(mid) 函數來驗證:「在 $K$ 次升級內,我們能不能讓所有挑選的邊,強度都 $\ge mid$?」

  3. 根據驗證結果,不斷縮小範圍,直到找到極限值。

💡 真實世界的應用場景:高擴充性的「萬用框架」

這個演算法雖然時間複雜度多了一個 $\log M$,但在真實的工程應用中,它卻具有壓倒性的擴充性 (Extensibility)!

  • 電信網路的 SLA 保證與預算規劃 中華電信或 AWS 要牽線連接全球的資料中心,並保證最低可用頻寬。公司今年只給了預算購買 $K$ 台「訊號放大器」。網路架構師會透過這個演算法「二分猜測」保證頻寬,驗證預算是否足夠,藉此找出基礎建設的投資報酬率極限。

  • EDA (電子設計自動化) 與晶片佈線 晶片設計中,工程師可以在線路上插入 Buffer(緩衝器)來增強訊號,但 Buffer 非常耗電且最多只能放 $K$ 個。軟體會猜測最差的訊號延遲時間,去驗證這 $K$ 個 Buffer 該怎麼放。

  • 為什麼它無可取代? 真實世界的規則往往不講武德。如果今天老闆說:「A 線路升級加 500、B 線路升級乘以 1.5、C 線路升級需要消耗 2 次升級機會...」純數學推導會瞬間崩潰,但二分搜尋版完全不受影響!你只需要在 check() 函數裡加上幾行 if-else,這個演算法就能完美存活。

策略二:Kruskal 演算法變形 (Pure Greedy)

這是一個將圖論數學性質發揮到極致的 $O(E \log E)$ 神級解法。它捨棄了「猜答案」,直接在一次遍歷中找出答案。

運作邏輯:

  1. 將所有「可選邊」依照強度由大到小排序。

  2. 依序將邊加入圖中(使用並查集 DSU 避免迴圈)。

  3. 既然有 $K$ 次升級機會,為了讓「最小值」最大化,自然要把機會留給生成樹中最弱的那 $K$ 條邊。

  4. 透過追蹤 edgesUsed,精準攔截出「沒有被升級的最弱邊」和「有被升級的最弱邊」,最後比較瓶頸即可。

💡 真實世界的應用場景:極致效能的「特製手術刀」

當規則明確且不變時,這種純貪心演算法能提供無與倫比的效能,特別適合底層系統與即時運算。

  • Linux Kernel 的生成樹協定 (STP) 在網路橋接系統 (net/bridge/br_stp.c) 中,為了解決交換機之間的「廣播風暴」,Kernel 必須在極短時間內找出無迴圈的生成樹。Kruskal 演算法的底層邏輯正是這類網路防護機制的核心。

  • 機器學習:層次分群 (Hierarchical Clustering) 在資料科學中 (例如 Single-linkage Clustering),我們需要將特徵相近的資料點分群。背後運作完全依賴排序與並查集 (DSU),能快速將距離最短的節點合併,達成自動分類。

  • 電腦視覺:影像分割 (Image Segmentation) 讓電腦看懂照片中哪裡是人、哪裡是背景。演算法將像素當作節點,顏色差異當作邊,透過並查集在極短的 $O(1)$ 時間內將相似區塊合併,達成即時去背效果。

總結

LeetCode 3600 教會我們最重要的一課是:演算法沒有絕對的好壞,只有最適合的情境。

  • 如果你面對的是一個規則單純、對效能要求極高的底層系統,請拿出 Kruskal 貪心法 這把特製手術刀。

  • 如果你面對的是一個業務邏輯複雜、需求隨時會變更的商業系統,請架構好 二分搜尋驗證 這個萬用防護罩。

下次在解題時,不妨多想一步:這段程式碼如果放到真實世界,它會扮演什麼樣的角色呢?

2025年10月7日 星期二

Union Find

今日練習的 1488. Avoid Flood in The City 可以用 Union Find 來增加一些執行效率,照例練習一下 C++/Python/Go/Rust 等程式語言。

C++

class UnionFind {
public:
    vector < int > root;
    UnionFind(int n) : root(n + 1) { iota(root.begin(), root.end(), 0); }
    int Find(int x) { return (x == root[x]) ? x : root[x] = Find(root[x]); }
    void UnionNext(int x) { root[x] = Find(x + 1); }
};
class Solution {
public:
    vector < int > avoidFlood(vector < int > & rains) {
        const int n = rains.size();
        UnionFind G(n);
        unordered_map < int, int > rainDay;
        rainDay.reserve(n);
        vector < int > ans(n, 1);
        for (int i = 0; i < n; i++) {
            const int lake = rains[i];
            if (lake > 0) {
                ans[i] = -1;
                G.UnionNext(i);
                auto it = rainDay.find(lake);
                if (it != rainDay.end()) {
                    int prev = it->second;
                    int dry = G.Find(prev + 1);
                    if (dry > i)
                        return {};
                    ans[dry] = lake;
                    G.UnionNext(dry);
                    it->second = i;
                } else {
                    rainDay[lake] = i;
                }
            }
        }
        return ans;
    }
};

Python3

class UnionFind:
    def __init__(self, n: int):
        self.root = [i for i in range(n + 1)]

    def find(self, x: int):
        if x == self.root[x]:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]

    def unionNext(self, x: int):
        self.root[x] = self.find(x + 1)


class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        n = len(rains)
        G = UnionFind(n)
        rainDay = {}
        ans = [1] * n
        for i, lake in enumerate(rains):
            if lake > 0:
                ans[i] = -1
                G.unionNext(i)
                if lake in rainDay:
                    prev = rainDay[lake]
                    dry = G.find(prev + 1)
                    if dry > i:
                        return []
                    ans[dry] = lake
                    G.unionNext(dry)
                rainDay[lake] = i
        return ans

Go

type UnionFind []int

func (parent UnionFind) Find(x int) int {
	if x == parent[x] {
		return x
	} else {
		parent[x] = parent.Find(parent[x])
		return parent[x]
	}
}
func (parent UnionFind) UnionNext(x int) {
	parent[x] = parent.Find(x + 1)
}

func avoidFlood(rains []int) []int {
	n := len(rains)
	arr := make([]int, n+1)
	for i := range n + 1 {
		arr[i] = i
	}
	G := UnionFind(arr)
	rainDay := map[int]int{}
	ans := make([]int, n)
    for i := range n {
        ans[i] = 1
    }
	for i, lake := range rains {
		if lake > 0 {
			ans[i] = -1
			G.UnionNext(i)
			if prev, ok := rainDay[lake]; ok {
				dry := G.Find(prev + 1)
				if dry > i {
					return []int{}
				}
				ans[dry] = lake
				G.UnionNext(dry)
			}
			rainDay[lake] = i
		}
	}
	return ans
}

Rust

pub struct UnionFind {
    parent: Vec< i32 >,
}
impl UnionFind {
    pub fn new(n: usize) -> Self {
        let parent = (0..=n).map(|i| i as i32).collect();
        Self{parent}
    }
    pub fn find(&mut self, x: i32) -> i32 {
        let x_usize = x as usize;
        if self.parent[x_usize] == x {
            return x
        }
        self.parent[x_usize] = self.find(self.parent[x_usize]);
        self.parent[x_usize]
    }
    pub fn union_next(&mut self, x: i32) {
        self.parent[x as usize] = self.find(x + 1)
    }
}

use std::collections::HashMap;

impl Solution {
    pub fn avoid_flood(rains: Vec < i32 >) -> Vec < i32 > {
        let n = rains.len();
        let mut uf = UnionFind::new(n);
        let mut pool = HashMap::< i32,i32 >::new();
        let mut ans = vec![1; n];
        for (i, &lake) in rains.iter().enumerate() {
            if lake > 0 {
                ans[i] = -1;
                uf.union_next(i as i32);
                if let Some(prev) = pool.get(&lake) {
                    let dry = uf.find(prev + 1);
                    if dry > i as i32 {
                        return vec![];
                    }
                    ans[dry as usize] = lake;
                    uf.union_next(dry);
                }
                pool.insert(lake, i as i32);
            }
        }
        ans
    }
}

解題筆記:運用 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)` 就能始終高效地定位到下一個可用的資源。 它是一個很好的例子,展示了如何將一個我們熟悉的資料結構進行微小的改造,來解決一個看似不相關、但本質相通的問題。