Решение задач «Практика «Скользящий максимум»»,
Программирование в Нижнем Новгороде

Продолжайте работу в том же проекте Smooth В классе MovingMaxTask реализуйте функцию максимума в скользящем окне. Для каждой точки найдите максимум всех предшествующих точек в окне указанного размера. Алгоритм должен работать эффективно, то есть тратить на обработку одной точки в среднем O(1) времени, вне зависимости от размера окна. Эта задача не так проста как кажется, поэтому ниже описана идея простого и компактного алгоритма, до которого, тем не менее, не так просто догадаться самостоятельно. Впрочем, у задачи существуют разные решения. Допустимы любые решения с требуемой сложностью. Идея алгоритма Итак, давайте как и в прошлой задаче MovingAverageTask хранить элементы текущего окна. Мы не хотим пересчитывать максимум заново на каждой точке — это даст сложность обработки O(WindowSize), что слишком медленно по условию. Поэтому используем вспомогательную структуру данных, которая поможет это делать быстрее. Будем отдельно хранить список только тех значений окна, которые потенциально могут стать максимумом в будущем. Значение не может стать максимумом, если после него в окно попало хоть одно значение больше него. Поэтому перед добавлением очередного элемента в этот список (будем считать, что добавляем мы справа) нужно удалить справа все элементы, меньшие нового. Несложно понять, что этот список будет упорядоченным, а значит максимум всех чисел в текущем окне будет в этом списке самым левым. Для хранения этого списка потенциальных максимумов пригодится структура данных Deque (LinkedList в языке C#), в которой эффективно добавлять и удалять элементы можно с обоих концов списка. Пример Рассмотрим как будут выглядеть окно и список максимумов на каждой итерации обработки последовательности 2, 6, 2, 1, 3, 2, 5, 8, 1 с окном размера 5. Таблица во вложении Отладьте реализацию с помощью приложенных модульных тестов. Запустите тестирующее приложение и объясните наблюдаемый результат.