ช่องว่างสูงสุดใน C++ (Maximum Gap)

ภาพรวมปัญหา

ให้อาเรย์ไม่เรียง หาความต่างสูงสุดระหว่างสมาชิกติดกันในอาเรย์ที่เรียงแล้ว

ตัวอย่าง

[12,3,9,1,17] → เรียง: [1,3,9,12,17] → max gap = 9-3 = 6

วิธีแก้ปัญหา: Bucket Sort (Pigeonhole Principle)

ไม่ต้องเรียงทั้งอาเรย์ ใช้ bucket n-1 ใบ
- หา minVal, maxVal
- gap = ceil((maxVal-minVal)/(n-1))
- ใส่ตัวเลข (ยกเว้น min/max) ลง bucket ตาม (val-minVal)/gap
- แต่ละ bucket เก็บ min/max ของตัวใน bucket
- วนหา gap ระหว่าง bucket.max กับ bucketถัดไป.min

โค้ด 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));
}

ผลลัพธ์

6

การวิเคราะห์ความซับซ้อน

• เวลา: O(n)
• พื้นที่: O(n)