หาความต่างระหว่างสมาชิกติดกันสูงสุดในอาร์เรย์หลังเรียงลำดับใน C++

ได้รับอาร์เรย์ที่ไม่ได้เรียงลำดับ งานคือหาความต่างระหว่างสมาชิกติดกัน (adjacent difference) ที่มากที่สุดในรูปแบบที่เรียงลำดับแล้ว ขั้นแรกคือเรียงอาร์เรย์จากน้อยไปมาก (หรือมากไปน้อยก็ได้) จากนั้นวนคำนวณ Arr[i+1] - Arr[i] และหาค่าสูงสุด

ตัวอย่าง

ตัวอย่างที่ 1

Input: Arr[] = [1, 5, 10, 2, 7]

Output: 3

คำอธิบาย: เรียงน้อยไปมาก: [1, 2, 5, 7, 10]

Arr[1]-Arr[0] = 1, Max=1
Arr[2]-Arr[1] = 3, Max=3
Arr[3]-Arr[2] = 2, Max=3
Arr[4]-Arr[3] = 3, Max=3

ตัวอย่างที่ 2

Input: Arr[] = [5, 11, 21, 15, 20]

Output: 6

คำอธิบาย: เรียงน้อยไปมาก: [5, 11, 15, 20, 21]

Arr[1]-Arr[0] = 6, Max=6
Arr[2]-Arr[1] = 4, Max=6
Arr[3]-Arr[2] = 5, Max=6
Arr[4]-Arr[3] = 1, Max=6

แนวทางแก้ปัญหา

1. รับอาร์เรย์เข้ามา
2. เรียงอาร์เรย์จากน้อยไปมาก (ascending)
3. ตั้งค่า MaxD = Arr[1] - Arr[0]
4. วนลูปจาก index 1 ถึง n-2 คำนวณ diff = Arr[i+1] - Arr[i]
5. ถ้า diff > MaxD ให้อัปเดต MaxD
6. คืนค่า MaxD

ตัวอย่างโค้ด (สมัยใหม่ ใช้ vector)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxAdjacentDiff(vector<int> arr) {
    if (arr.size() < 2) return 0;
    
    sort(arr.begin(), arr.end());  // เรียงน้อยไปมาก
    
    int maxD = arr[1] - arr[0];
    for (size_t i = 1; i + 1 < arr.size(); ++i) {
        int diff = arr[i + 1] - arr[i];
        if (diff > maxD) maxD = diff;
    }
    return maxD;
}

int main() {
    vector<int> Arr = {1, 5, 2, 18, 20, 13};
    cout << "Maximum adjacent difference in sorted array: " 
         << maxAdjacentDiff(Arr) << endl;
    return 0;
}

ผลลัพธ์

Maximum adjacent difference in sorted array: 8

เรียง: {1,2,5,13,18,20} → diff: 1,3,8,5,2 → max = 8

โค้ดแบบคลาสสิก (array แบบดิบ)

#include <iostream>
#include <algorithm>
using namespace std;

int max_adj_Diff(int A[], int size) {
    if (size < 2) return 0;
    sort(A, A + size);
    int MaxD = A[1] - A[0];
    for (int i = 1; i < size - 1; i++) {
        if (A[i+1] - A[i] > MaxD)
            MaxD = A[i+1] - A[i];
    }
    return MaxD;
}

int main() {
    int Arr[] = {1, 5, 2, 18, 20, 13};
    int n = sizeof(Arr) / sizeof(Arr[0]);
    cout << "Maximum adjacent difference: " << max_adj_Diff(Arr, n) << endl;
    return 0;
}

ข้อสังเกต

• การเรียงลำดับใช้เวลา O(n log n) ซึ่งเป็น bottleneck หลัก
• หากต้องการ O(n) สามารถใช้ Bucket Sort / Pigeonhole Principle ได้ (เหมาะสำหรับข้อมูลที่มีช่วงค่าจำกัด)
• โจทย์นี้เกี่ยวข้องกับ "Maximum Gap" problem (LeetCode 164)