題目敘述
題目會給定一個有n個整數的陣列nums和指定的k值，問我們長度為k的子陣列的平均值的最大值是多少?
測試範例
Example 1:
Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75
Example 2:
Input: nums = [5], k = 1
Output: 5.00000
約束條件
Constraints:
n == nums.length
n 為輸入陣列的長度。
1 <= k <= n <= 10^5
k 值 一定<= n，而且介於1 ~ 10^5之間。
-10^4 <= nums[i] <= 10^4
每個陣列元素一定介於-10^4 ~ 10^4 之間。
演算法
長度為k的子陣列的平均值
= 長度為k的子陣列的總和 / k
= (1/k) * 長度為k的子陣列的總和
原本題目的要求 長度為k的子陣列平均值的最大值
等價於 一個長度為k的滑動窗口總和取最大值，最後再除以k。
程式碼
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
# Concept:
# MaxAverage is equivelent to (MaxPartialSum/k)
# Use sliding windows to maintain MaxPartialSum
sum_of_sliding_window = sum( nums[0:k] )
max_sum = sum_of_sliding_window
for i in range(k, len(nums) ):
# update sum of sliding window
sum_of_sliding_window += ( nums[i] - nums[i-k] )
max_sum = max( max_sum, sum_of_sliding_window )
return max_sum/k
