[LeetCode] Maximum Average Subarray I

1.문제

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.

n개의 숫자로 이루어진 정수배열이 주어지고 정수 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
• 1 <= k <= n <= 10^5
• -10^4 <= nums[i] <= 10^4

2.풀이

1. 배열의 가장 앞에서부터 k개씩 부분배열을 만든다.
2. 부분배열의 합을 구하여 현재까지의 최댓값과 비교를 하여 최댓값을 갱신한다.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
const findMaxAverage = function (nums, k) {
  let left = 0;
  let largestTotal = 0;
  let currentTotal = 0;

  // 처음 k 길이의 부분 배열의 합 구하기
  for (let i = 0; i < k; i++) {
    currentTotal += nums[i];
  }

  // 현재 가장 큰 총합이 처음 구한 총합이다.
  largestTotal = currentTotal;

  // k번째 요소부터 하나씩 늘려가면서 총합을 구한다.
  for (let right = k; right < nums.length; right++) {
    currentTotal -= nums[left++];
    currentTotal += nums[right];
    // 만약 현재 총합이 최대 총합보다 크면 갱신
    largestTotal = currentTotal > largestTotal ? currentTotal : largestTotal;
  }

  // 평균 리턴
  return largestTotal / k;
};

3.결과