LeetCode 179 最大數：自定義比較器排序拼接

問題描述

給定一組非負整數，重新排列它們的順序使之組成一個最大的整數。例如 [3,30,34,5,9] → "9534330"。結果可能很大，返回字符串。

核心思想：自定義排序規則

關鍵在於定義兩個數字 a 和 b 的「大小」：比較拼接字符串 ab 和 ba 的字典序（或數值）。若 ab > ba，則 a 應排在 b 前面。

正確性證明略述

• 排序後拼接保證任意相鄰對滿足 a_i a_{i+1} ≥ a_{i+1} a_i。
• 由傳遞性可推導整體最大（需證明比較器滿足嚴格弱序，實際上 ab > ba 定義的關係是可傳遞的）。

關鍵代碼 (Java)

public String largestNumber(int[] nums) {
    String[] strs = new String[nums.length];
    for (int i = 0; i < nums.length; ++i) strs[i] = String.valueOf(nums[i]);

    Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b)); // 降序

    if (strs[0].equals("0")) return "0"; // 全零情況
    return String.join("", strs);
}

關鍵細節

1. 字符串比較：直接比較 a+b 和 b+a 的字典序等價於數值比較（因長度相同）。
2. 全零處理：輸入如 [0,0] 應返回 "0" 而非 "00"。
3. 比較器方向：(b+a).compareTo(a+b) 實現降序（大的在前）。

複雜度分析

• 時間：O(n log n * k) — n 為數組長度，k 為數字平均字符串長度（比較器開銷）。
• 空間：O(n) — 存儲字符串數組。

擴展：C++ 實現

string largestNumber(vector& nums) {
    vector strs;
    for (int n : nums) strs.push_back(to_string(n));
    sort(strs.begin(), strs.end(), [](const string& a, const string& b) {
        return a + b > b + a;
    });
    if (strs[0] == "0") return "0";
    string res;
    for (auto& s : strs) res += s;
    return res;
}

總結

LeetCode 179 展示了「自定義比較器排序」的強大威力。核心洞見是：局部最優拼接順序（ab vs ba）能推導出全局最優。此類「排序後拼接」問題（如組成最小數、圍牆問題）均可用同套思路解決。