[LeetCode] 643. Maximum Average Subarray I 해설 및 풀이 (Python)

LeetCode 643. Maximum Average Subarray I

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

 

---

 

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.

 

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
1 <= k <= n <= 105
-104 <= nums[i] <= 104

 

한글 해석

 

nums요소 로 구성된 정수 배열 n과 정수가 주어집니다 k.

길이가 와 같고 k 평균값이 최대인 연속 부분 배열을 찾아 그 값을 반환하세요 . 계산 오류가 보다 작은 답은 모두 허용됩니다.10-5

 

예시 1:

입력: nums = [1,12,-5,-6,50,3], k = 4
 출력: 12.75000
 설명: 최대 평균은 (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75입니다.

 

예 2:

입력: nums = [5], k = 1
 출력: 5.00000
 

제약 조건:

n == nums.length
1 <= k <= n <= 105
-104 <= nums[i] <= 104

 

---

문제 유형

Array

Sliding Window

 

풀이 방법 도출

 

슬라이딩 윈도우(Sliding Window) 알고리즘을 사용하여 이 문제를 해결할 수 있습니다.

 

1. 길이가 k인 첫 번째 윈도우의 합을 먼저 계산합니다.
2. 매번 한 칸씩 오른쪽으로 윈도우를 이동하며 합을 업데이트 합니다.
3. 새로 추가된 값은 더하고, 빠진 값은 뺍니다.
4. 각 윈도우의 합 중 최댓값 합 / k를 출력합니다.

 

 

시간 복잡도

• O(N)

---

핵심 코드 삽입 및 설명

 

from typing import List

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        n = len(nums)
        max_sum = sum(nums[:k])
        current_sum = max_sum
        
        for i in range(k, n):
            current_sum += nums[i] - nums[i - k]
            max_sum = max(max_sum, current_sum)
        
        return max_sum / k