Решение задачи #22. Python Яндекс CodeRun, Минимум на отрезке

Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Категория: Алгоритмы.
Название задачи: Минимум на отрезке.
Сложность: Средняя.
Статус решения: "Решено".

Условие задачи:
Рассмотрим последовательность целых чисел длины nn.

По ней двигается «окно» длины kk: сначала в «окне» находятся первые kk чисел, на следующем шаге в «окне» уже будут находиться kk чисел, начиная со второго, и так далее до конца последовательности.

Требуется для каждого положения «окна» определить минимум в нём.

Решение:

Python

from collections import deque

def sliding_window_min(nums, k):
    """Находит минимальное значение в каждом окне длины k.

    Args:
        nums: Список чисел.
        k: Размер окна.

    Returns:
        Список минимальных значений для каждого окна.
    """

    n = len(nums)
    q = deque()  # Дека для хранения индексов
    result = []

    for i in range(n):
        # Удаляем индексы элементов, выходящих за пределы окна
        while q and q[0] <= i - k:
            q.popleft()

        # Добавляем текущий индекс в деку
        while q and nums[q[-1]] >= nums[i]:
            q.pop()
        q.append(i)

        # Минимальное значение в текущем окне находится в начале деки
        if i >= k - 1:
            result.append(nums[q[0]])

    return result

def main():
    n, k = map(int, input().split())
    nums = list(map(int, input().split()))
    result = sliding_window_min(nums, k)
    print(*result)

if __name__ == '__main__':
    main()
	

Объяснение кода

Дека:
Используется для хранения индексов элементов, а не самих элементов. Это позволяет эффективно удалять элементы с обоих концов.

Удаление элементов:
Элементы удаляются из деки, если они выходят за пределы текущего окна или если существует меньший элемент справа.

Добавление элементов:
Текущий индекс добавляется в конец деки.

Минимальное значение:
Индекс минимального элемента в текущем окне всегда находится в начале деки.

Асимптотическая сложность:
Время работы алгоритма составляет O(n), где n - длина последовательности. Это достигается за счет того, что каждый элемент добавляется и удаляется из деки не более одного раза.

Источник решения: hdhai.com