643. Maximum Average Subarray I

643. Maximum Average Subarray I

題目不難，但是小細節很多，這個題目主要的考點是滑動窗口。

最一開始的想法是每次移動一個 index ，並且加總接下來 k 個元素，在這個過程中，更新記憶體中的最大值。

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        
        res = float('-inf')
        
        for i in range(len(nums) - k + 1):
            tmp = 0
            for j in range(i, i + k):
                tmp += nums[j]
            res = max(res, tmp)
        
        return res / k

這樣的確透過滑動窗口來完成這個題目了，但是此時的時間複雜度是 \(O(n * k)\)，因為每次更新一個窗口時，需要再遍歷 k 個元素，此時我們想要試著看看可不可以優化這個演算法？

每次更新這個窗口的時，其實我們真正變動的地方在於踢除最舊的元素，以及加入新的元素，中間的元素其實是沒有必要變動的。

這時候，可以把時間複雜度將至 \(O( n + 2)\approx O(n)\)。

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        
        res = float('-inf')
        tmp = 0
        for i in range(k):
            tmp += nums[i]
        res = max(res, tmp)
        
        for i in range(k, len(nums)):
            tmp = tmp - nums[i - k] + nums[i]
            res = max(res, tmp)
        
        return res / k

While loop 的做法

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        
        curr = 0
        res = float('-inf')
        slow = 0
        fast = 0
        n = len(nums)
        
        while fast < n:
            curr += nums[fast]
            if fast - slow + 1 > k:
                curr -= nums[slow]
                slow += 1
            if fast - slow + 1 == k:
                res = max(res, curr)
            
            fast += 1
        
        return res/k