[LeetCode] 643. Maximum Average Subarray I

問題

https://leetcode.com/problems/maximum-average-subarray-i/description/

解答と解説

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        curTotal = 0
        # 0からkまでの初期値
        for i in range(k):
            curTotal += nums[i]
        maxTotal = curTotal

        for right in range(k, len(nums)):
            # 足して引く
            curTotal = curTotal + nums[right] - nums[right - k]
            # 最大値の比較
            maxTotal = max(maxTotal, curTotal)
        
        return maxTotal / k

numsの配列の要素数をnとした時、

• Time Complexity: O(n)
• Space Complexity: O(1)

固定長のSliding Windowの典型パターン。

平均値の最大値が求められているが、割る数がkで固定されているので割り算による微妙な値のズレを回避するため合計値で比較して最後にkで割るようにしている。