리트코드 - 643. Maximum Average Subarray I

https://leetcode.com/problems/maximum-average-subarray-i/description/?envType=study-plan-v2&envId=leetcode-75

Maximum Average Subarray I - LeetCode

 

n개의 요소로 구성된 정수 배열 num과 정수 k가 주어지면 최대 평균값을 갖는 길이가 k인 연속적인 하위 배열을 찾아 그 배열 요소들의 평균 값을 반환하는 문제이다.

 

연속적인 하위 배열이므로 시작 인덱스와 끝 인덱스를 저장해두고 한 칸씩 이동시키면서 각 하위 배열의 요소들의 합이 가장 큰 값의 평균을 구해주면 된다.

 

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        tmp = sum(nums[:k]) # O(k) 
        res = tmp
        for i in range(1, len(nums) - k + 1): # O(n - k) 
            tmp = tmp - nums[i-1] + nums[i + k - 1] # O(1)
            res = max(tmp, res) # O(1)

        return res / k

 

전체 시간 복잡도는 O(k) + O(n-k) = O(n)이다.

추가적인 공간을 거의 사용하지 않는다. tmp와 res 변수만 사용되며, 따라서 공간 복잡도는 O(1) 이다