โปรแกรมหาค่าเฉลี่ยสูงสุดของสับลิสต์ที่มีขนาดอย่างน้อย k ใน Python

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

ให้รายการตัวเลข nums และค่า k ต้องการหาค่าเฉลี่ยสูงสุดของสับลิสต์ (subarray ต่อเนื่อง) ใดๆ ที่มีความยาว ≥ k

ตัวอย่าง

nums = [2, 10, -50, 4, 6, 6], k = 3 → เอาต์พุต: 5.333... (จากสับลิสต์ [4, 6, 6])

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

ใช้ Binary Search บนคำตอบ (ค่าเฉลี่ย) + Prefix Sum + Sliding Window:

1. Binary search ค่าเฉลี่ยระหว่าง min(nums) ถึง max(nums)
2. สำหรับ mid (ค่าเฉลี่ยที่ทดสอบ): ตรวจสอบว่ามี subarray ยาว ≥ k ที่มีเฉลี่ย ≥ mid หรือไม่
3. แปลงเป็น: มี subarray ที่ sum(nums[i] - mid) ≥ 0 หรือไม่
4. ใช้ prefix sum และติดตาม minimum prefix sum ที่อยู่ก่อนหน้าอย่างน้อย k ตำแหน่ง

โค้ด Python

class Solution:
    def solve(self, nums, k):
        left, right = min(nums), max(nums)
        s = sum(nums[:k])
        largest_avg = s / k
        
        while left <= right:
            mid = (left + right) // 2
            sum1 = s
            avg = s / k
            sum2 = 0
            cnt = 0
            
            for i in range(k, len(nums)):
                sum1 += nums[i]
                sum2 += nums[i - k]
                cnt += 1
                avg = max(avg, sum1 / (cnt + k))
                if sum2 / cnt <= mid:
                    sum1 -= sum2
                    cnt = 0
                    sum2 = 0
                avg = max(avg, sum1 / (cnt + k))
            
            largest_avg = max(largest_avg, avg)
            if avg > mid:
                left = mid + 1
            else:
                right = mid - 1
        
        return largest_avg

ob = Solution()
nums = [2, 10, -50, 4, 6, 6]
k = 3
print(ob.solve(nums, k))

อินพุต

[2, 10, -50, 4, 6, 6], k = 3

เอาต์พุต

5.333333333333333