Maximum Average Subarray I

Лёгкая№643фиксированный размер

Дан массив чисел и длина k. Среди всех отрезков из k чисел подряд найди наибольшее среднее. Наш пример: [5, -3, 4, 8, -2, 6, -7] и k = 4 — ответ 4: отрезок [4, 8, -2, 6] даёт сумму 16, а 16 / 4 = 4.

643 Maximum Average Subarray IРазбор · 1×

Пример: [5, -3, 4, 8, -2, 6, -7], k = 4. Всё делает один цикл: число на right входит, число на right - k выходит.

051-324384-2566-7sum0best–
ещё не дошлиокновходящее числоуходящее числовышло из окналучшее окно

Начинаем с пустого окна: sum = 0

01/38
сначала · назад · пуск · шаг
Скорость
1function findMaxAverage(nums, k):
2 sum = 0
3 best = -infinity
4 for right from 0 to len(nums) - 1:
5 sum = sum + nums[right]
6 if right >= k:
7 sum = sum - nums[right - k]
8 if right >= k - 1:
9 best = max(best, sum)
10 return best / k
состояние
sum
0
best
–
right
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. У двух соседних окон k - 1 общих чисел. Поэтому новая сумма — это старая плюс вошедшее число минус ушедшее: O(1) за шаг вместо того, чтобы снова складывать k чисел.
  2. Длина у всех окон одна — k, поэтому наибольшая сумма и есть наибольшее среднее. Сравниваем суммы, числа остаются целыми, а делим один раз, в конце.
  3. best начинается с -∞, а не с 0: если бы все числа были отрицательными, все суммы были бы меньше 0, и best = 0 стал бы неверным ответом.

Сложность

Время O(n): каждое число один раз входит в окно и один раз выходит. Память O(1): только сумма, best и индекс.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.