UniLecs #186. Максимум в подмассивах

Задача: дан массив целых чисел Arr, а также натуральное число K. Необходимо найти максимум для каждого из подмассива размера K.

Входные данные: Arr - массив целых чисел размера от 1 до 10^5. K - натуральное число от 1 до 10^5. K <= Arr.Length.

Вывод: список максимумов для каждого из подмассива размера K.

Пример: Arr = -5, 1, -6, 2, 5; K = 3;

Answer = 1, 2, 5 (1 = Max(-5, 1, -6), 2 = Max(1, -6, 2), 5 = Max(-6, 2, 5)).

Идея: воспользуемся списком размером K, где можно добавлять/удалять элементы на обоих концах списка. Это так называемая двустороння очередь (Deque). Эта "очередь" хранит только "полезные" индексы элементов текущего подмассива.

Элемент полезен, если он находится в текущем подмассиве и больше, чем все остальные элементы слева от него в текущем подмассиве. Обрабатываем все элементы массива и поддерживаем "очередь" так, чтобы она содержала "полезные" элементы текущего подмассива, и эти "полезные" элементы поддерживаются в отсортированном порядке. Т.е. элемент в передней части очереди является наибольшим, а элемент в задней части очереди является наименьшим из текущего подмассива.

Давайте разберем на примере: Arr = [-5, 1, -6, 2, 5]; K = 3;

1. [(-5, 1, -6), 2, 5]

Deque: { 1 } (индекс элемента со значением 1, т.к. Max(-5, 1, -6) = 1)

Max Element = 1;

2. [-5, (1, -6, 2), 5]

Deque: { 1, 3 } (добавляем 3 - индекс элемента со значением 2, т.к. Max(1, -6, 2) = 2)

Max Element = 2;

3. [-5, 1, (-6, 2, 5)]

Deque: { 3, 4 } (добавляем 4 - индекс элемента со значением 5, т.к. Max(-6, 2, 5) = 5)

Max Element = 5;

Реализация: