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