Maximum Gap

Sizga butun sonlardan iborat nums massivi berilgan. Uni tartiblagandan (sorted) so'ng qo'shni elementlar orasidagi maksimal farqni toping. Agar massivda 2 tadan kam element bo'lsa, 0 qaytaring.

Algoritm chiziqli vaqt (O(n)) va chiziqli qo'shimcha xotira (O(n)) ishlatib ishlashi kerak (masalan, Radix Sort yoki Bucket Sort).

func solve(nums []int) int {
    // ...
}

Misollar

Input: nums = [3,6,9,1]
Output: 3
Tushuntirish: Tartiblangandan so'ng [1,3,6,9]. Qo'shni elementlar o'rtasidagi farq: (3-1)=2, (6-3)=3, (9-6)=3. Maksimal farq 3 ga teng.

Input: nums = [10]
Output: 0

Input: nums = [1,10000000]
Output: 9999999

Maslahatlar

1. Solishtirishga asoslangan saralash O(n log n) beradi, lekin bizga O(n) kerak — bu yerda Bucket Sort g'oyasidan foydalaning: agar sonlarni (max-min)/(n-1) hajmidagi "chelaklar"ga taqsimlasangiz, javob hech qachon bitta chelak ICHIDA bo'lmaydi, faqat chelaklar ORASIDA bo'ladi.
2. Har bir chelakda faqat minimum va maksimum qiymatlarni saqlash yetarli (chelak ichidagi tartib ahamiyatsiz, chunki maksimal farq ikki qo'shni to'lgan chelak orasida bo'ladi). Chelaklarni to'ldirib bo'lgach, ketma-ket to'lgan chelaklar bo'ylab yurib, oldingi chelakning maksimumi bilan joriy chelakning minimumi orasidagi farqni hisoblab, eng kattasini toping.