付費限定文章

最大平均子陣列 Maximum Average Subarray I_Leetcode #643 精選75題

Pawel Czerwinski on Unsplash

題目敘述

題目會給定一個有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