LeetCode Maximum Gap 完整解析

給定無序陣列，求排序後相鄰元素最大差值。要求 O(N) 時間空間。陣列長度 < 2 返回 0。元素為非負 32 位整數。

核心思想：桶排序 + 抽屜原理

設最小值 min、最大值 max、桶數 = n（陣列長度）。
桶寬 gap = (max - min) / n + 1（向上取整）。
最大間隙必發生在桶與桶之間，而非桶內（桶內最大差值 < gap）。

演算法步驟

1. 掃描求 min, max
2. 建立 n 個桶，每桶記錄 min, max
3. 將每個數放入對應桶：idx = (num - min) / gap
4. 遍歷桶，記錄非空桶的 min，與前一非空桶的 max 差值更新答案

完整 AC 程式碼

class Solution {
    struct Bucket { int min = INT_MAX, max = INT_MIN; bool used = false; };
public:
    int maximumGap(vector& nums) {
        int n = nums.size();
        if (n <= 1) return 0;
        
        int mn = *min_element(nums.begin(), nums.end());
        int mx = *max_element(nums.begin(), nums.end());
        if (mn == mx) return 0;
        
        int gap = (mx - mn) / n + 1; // 桶寬
        vector buckets(n);
        
        for (int num : nums) {
            int idx = (num - mn) / gap;
            Bucket& b = buckets[idx];
            b.used = true;
            b.min = min(b.min, num);
            b.max = max(b.max, num);
        }
        
        int ans = 0;
        int prev_max = mn;
        for (const auto& b : buckets) {
            if (!b.used) continue;
            ans = max(ans, b.min - prev_max);
            prev_max = b.max;
        }
        return ans;
    }
};

關鍵點總結

• 桶數 = n：保證至少一個空桶（抽屜原理），最大間隙 ≥ 桶寬
• 桶寬向上取整：(max-min)/n + 1 確保桶內差值 < 桶寬
• 只需記錄桶內 min/max：桶內順序無關
• 首尾處理：prev_max 初始為 mn，最後桶的 max 必為 mx
• 時間空間 O(N)：滿足題目要求