โปรแกรมหาความต่างสูงสุดระหว่างตัวเลขกับตัวเลขที่น้อยกว่าถัดไปใน Python

คำอธิบายโจทย์

ให้รายการตัวเลข nums ต้องการหาความต่างสูงสุดระหว่างตัวเลขใดตัวเลขหนึ่งกับตัวเลขที่น้อยกว่ามันที่สุด (next smaller number) โดยต้องแก้ในเวลา O(n)

ตัวอย่าง

nums = [14, 2, 6, 35, 12] → เอาต์พุต: 21 (จาก 35 - 14 = 21)

วิธีแก้ปัญหา

ใช้ Bucket Sort / Pigeonhole Principle:

1. หาค่า min_val และ max_val ของอาเรย์
2. คำนวณ bucket size: delta = (max_val - min_val) / (n - 1)
3. กระจายตัวเลขเข้า buckets โดยแต่ละ bucket เก็บค่า min และ max ของช่วงนั้น
4. คำตอบต้องมาจาก max ของ bucket ก่อนหน้า - min ของ bucket ถัดไป (ไม่ใช่ภายใน bucket เดียวกัน)
5. สแกน buckets ตามลำดับ คำนวณความต่างระหว่าง bucket ที่มีค่า

โค้ด Python

from collections import defaultdict
import math

class Solution:
    def solve(self, nums):
        max_val = max(nums)
        min_val = min(nums)
        if max_val == min_val:
            return 0
        
        delta = (max_val - min_val) / (len(nums) - 1)
        min_map = defaultdict(lambda: float("inf"))
        max_map = defaultdict(lambda: float("-inf"))
        
        for num in nums:
            idx = math.floor((num - min_val) / delta)
            max_map[idx] = max(max_map[idx], num)
            min_map[idx] = min(min_map[idx], num)
        
        res = 0
        prev = min_val
        for i in range(len(nums)):
            if min_map[i] != float("inf"):
                res = max(res, min_map[i] - prev)
                prev = max_map[i]
        
        return res

ob = Solution()
nums = [14, 2, 6, 35, 12]
print(ob.solve(nums))

อินพุต

[14, 2, 6, 35, 12]

เอาต์พุต

21