LeetCode 164：最大間距——桶排序實現線性時間

題目描述

給定無序數組，求排序後相鄰元素的最大差值。要求線性時間/空間，元素為非負 32 位整數。

桶排序核心思想

1. 找出最小值 min 和最大值 max
2. 平均間距 gap = ceil((max - min) / (n - 1))
3. 建立 n-1 個桶，第 k 個桶覆蓋 [min + k*gap, min + (k+1)*gap)
4. 將除 min、max 外的元素放入對應桶，只記錄桶內最小/最大值
5. 最大間距必出現在相鄰非空桶之間，或 min 與第一個非空桶、最後非空桶與 max 之間

鴿巢原理證明

n 個元素放入 n-1 個桶 ⇒ 至少一個桶為空 ⇒ 最大間距 ≥ gap ⇒ 同桶內間距不可能是答案，只需檢查桶間間距。

C++ 實現

int maximumGap(vector<int>& num) {
    if (num.size() < 2) return 0;
    int mn = *min_element(num.begin(), num.end());
    int mx = *max_element(num.begin(), num.end());
    if (mn == mx) return 0;

    int n = num.size();
    int gap = (mx - mn - 1) / (n - 1) + 1; // ceil
    vector<int> bucketMin(n - 1, INT_MAX), bucketMax(n - 1, INT_MIN);

    for (int v : num) {
        if (v == mn || v == mx) continue;
        int idx = (v - mn) / gap;
        bucketMin[idx] = min(bucketMin[idx], v);
        bucketMax[idx] = max(bucketMax[idx], v);
    }

    int maxGap = 0, prev = mn;
    for (int i = 0; i < n - 1; ++i) {
        if (bucketMin[i] == INT_MAX) continue; // 空桶
        maxGap = max(maxGap, bucketMin[i] - prev);
        prev = bucketMax[i];
    }
    maxGap = max(maxGap, mx - prev);
    return maxGap;
}

複雜度

• 時間：O(n) —— 三次線性掃描
• 空間：O(n) —— 桶數組

效能圖示