Premium

Скользящее окно

Максимальное среднее подмассива I

Найти максимальное среднее значение подмассива фиксированной длины

Легкий

Постановка задачи

Описание (LeetCode - 643. Maximum Average Subarray I)

Дан массив целых чисел nums и число k. Нужно найти непрерывный подмассив длины k с максимальным средним значением и вернуть это значение.

Пример 1:

nums = [1, 12, -5, -6, 50, 3], k = 4

Результат:

12.75

Пояснение:

Максимальное среднее значение дает подмассив [12, -5, -6, 50]:

(12 - 5 - 6 + 50) / 4 = 12.75

Пример 2:

nums = [5], k = 1

Результат:

5.0

Ограничения:

  • 1 <= k <= nums.length <= 10⁵
  • -10⁴ <= nums[i] <= 10⁴

Решение

Нам нужно найти подмассив фиксированной длины k. Наивное решение для каждого начала подмассива - заново считать сумму k элементов. Таких подмассивов `n - k

  • 1, и каждый пересчет занимает O(k), поэтому получится сложность O(n * k)`.

Скользящее окно позволяет не пересчитывать сумму целиком.

Идея решения:

Сначала посчитаем сумму первых k элементов. Это первое окно. Затем будем сдвигать окно на один элемент вправо:

  1. Добавляем новый правый элемент.
  2. Вычитаем старый левый элемент.
  3. Обновляем максимальную сумму окна.

Среднее значение максимально тогда, когда максимальна сумма окна, потому что длина окна всегда равна k.

Основные шаги:

  1. Считаем сумму первых k элементов и сохраняем ее в windowSum.
  2. Инициализируем maxSum = windowSum.
  3. Идем правой границей от k до конца массива.
  4. На каждом шаге:
    • добавляем nums[right];
    • вычитаем nums[right - k];
    • обновляем maxSum.
  5. Возвращаем maxSum / k.

Рассмотрим пример:

nums = [1, 12, -5, -6, 50, 3], k = 4

Первое окно:

[1, 12, -5, -6], сумма = 2

Сдвигаем окно:

[12, -5, -6, 50], сумма = 51

Еще один сдвиг:

[-5, -6, 50, 3], сумма = 42

Максимальная сумма равна 51, значит ответ:

51 / 4 = 12.75

Это пример фиксированного окна. Его размер всегда равен k, поэтому нам не нужно решать, когда сужать окно. Левая граница сдвигается автоматически вместе с правой.

Оценка сложности

Временная сложность

Мы один раз считаем первое окно и затем один раз проходим по оставшимся элементам. Итоговая временная сложность: O(n).

Пространственная сложность

Мы используем только несколько переменных, поэтому дополнительная память равна O(1).

Код решения

Приведем код решения.

func findMaxAverage(nums []int, k int) float64 {
    windowSum := 0
    for i := 0; i < k; i++ {
        windowSum += nums[i]
    }
    maxSum := windowSum
    for right := k; right < len(nums); right++ {
        windowSum += nums[right] - nums[right-k]
        maxSum = max(maxSum, windowSum)
    }
    return float64(maxSum) / float64(k)
}

Итоги

Фиксированное скользящее окно работает за счет инкрементального обновления суммы. При каждом сдвиге мы добавляем один элемент и убираем один элемент, вместо того чтобы заново считать сумму всего подмассива.

Войдите чтобы отмечать прогресс