Khoảng cách lớn nhất (Maximum Gap) trong C++

Cho mảng không sắp xếp, tìm khoảng cách lớn nhất giữa 2 phần tử liên tiếp trong mảng đã sắp xếp. Trả về 0 nếu n < 2.

Ví dụ

[12,3,9,1,17] → Sorted: [1,3,9,12,17] → Max gap = 9-3 = 6.

Thuật toán: Bucket Sort (Pigeonhole Principle)

Không sắp xếp toàn bộ (O(n log n)), dùng bucket:

1. Tìm minVal, maxVal.
2. gap = ceil((maxVal - minVal) / (n - 1)) — kích thước bucket tối thiểu.
3. Tạo n-1 bucket, mỗi bucket lưu min và max của các số rơi vào đó.
4. Phân phối các số (trừ min/max) vào bucket: idx = (num - minVal) / gap.
5. Duyệt bucket, max gap = max(bucket[i].min - prev_max).

Tại sao đúng? Gap lớn nhất ≥ gap (nguyên lý chuồng bồ câu), nên 2 số tạo ra max gap chắc chắn ở 2 bucket khác nhau.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        lli minVal = INT_MAX, maxVal = INT_MIN;
        int n = nums.size();
        if (n < 2) return 0;
        for (int x : nums) {
            minVal = min(minVal, (lli)x);
            maxVal = max(maxVal, (lli)x);
        }
        int gap = ceil((double)(maxVal - minVal) / (n - 1));
        vector<int> bucketMax(n-1, INT_MIN), bucketMin(n-1, INT_MAX);
        for (int x : nums) {
            if (x == minVal || x == maxVal) continue;
            int idx = (x - minVal) / gap;
            bucketMax[idx] = max(bucketMax[idx], x);
            bucketMin[idx] = min(bucketMin[idx], x);
        }
        lli ret = 0, prev = minVal;
        for (int i = 0; i < n-1; i++) {
            if (bucketMax[i] == INT_MIN) continue;
            ret = max(ret, (lli)bucketMin[i] - prev);
            prev = bucketMax[i];
        }
        return max(ret, maxVal - prev);
    }
};

int main() {
    Solution ob;
    vector<int> v = {12, 3, 9, 1, 17};
    cout << ob.maximumGap(v);
    return 0;
}

Độ phức tạp

• Thời gian: O(n) — 1 lần duyệt tìm min/max, 1 lần phân bucket, 1 lần duyệt bucket.
• Không gian: O(n).

Input / Output

Input:  [12,3,9,1,17]
Output: 6