День 72: Максимальное значение в скользящем окне на Python - решение с использованием двусвязной очереди O(n) для эффективного отслеживания максимальных значений (Руководство по задаче #239 на LeetCode)

72-й день вызова программирования был сосредоточен на решении проблемы максимального значения в скользящем окне с использованием Python. Основное решение использует двустороннюю очередь для эффективного нахождения максимального значения в каждом скользящем окне размера *k* в массиве. Этот подход достигает временной сложности O(n), превосходя наивные методы O(nk). Функция, названная `sliding_window_max`, принимает массив и размер окна в качестве входных данных и возвращает список максимумов. Двусторонняя очередь используется для хранения индексов, гарантируя, что в начале очереди всегда находится индекс максимального значения в текущем окне. Алгоритм проходит через массив, удаляя устаревшие индексы и меньшие значения из очереди перед добавлением текущего индекса. Индексы добавляются в окно только после достижения размера окна. Когда окно завершено, максимальное значение добавляется в список результатов. Эта реализация подходит для потоковых данных, анализа акций и запросов максимальных значений в реальном времени. Скрипт также включает основной раздел для ввода и вывода пользователя. Хранение индексов имеет решающее значение для проверки валидности окна внутри очереди. Монотонно убывающая свойство гарантирует, что в начале очереди всегда находится максимальное значение. Решение подчеркивает отслеживание индексов и амортизированную обработку O(1).