Минимум в скользящем окне
Нужно реализовать скользящий минимум. Для заданного массива чисел и числа K найти минимумы для всех отрезков длины K. Я решил сделать это с помощью обычных срезов, но вот скорость такого подхода - квадратичная, а нужна линейная.
n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(n-k+1):
print(min(a[i:-1]))
Как сделать умней?
Ответы (1 шт):
Автор решения: passant
→ Ссылка
Вообще-то скользящий минимум это не
min(a[i:-1])
а
min(a[i:i+k])
И соответственно скорость (конечно, не скорость, а сложность, ну да ладно) -
O(n*k) т.е. практически O(n)