Cho danh sách nums và giá trị k, tìm giá trị trung bình lớn nhất của bất kỳ dãy con nào có độ dài ≥ k.
Ví dụ: nums = [2, 10, -50, 4, 6, 6], k = 3 → kết quả 5.333... (dãy [4, 6, 6]).
Giải pháp
Sử dụng tìm kiếm nhị phân trên đáp án kết hợp kiểm tra khả thi:
- left = min(nums), right = max(nums)
- Lặp while left <= right:
- mid = (left + right) // 2
- Kiểm tra xem có dãy con độ dài ≥ k có trung bình > mid không
- Dùng kỹ thuật prefix sum và cửa sổ trượt để kiểm tra trong O(n)
- Cập nhật left/right dựa trên kết quả kiểm tra
Ví dụ minh họa
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))
Đầu vào
[2, 10, -50, 4, 6, 6], k = 3
Đầu ra
5.333333333333333