Задача с собеседования в Яндекс.
Пусть задан массив из n целых чисел. По этому массиву будут ходить два указателя l и r (0 ≤ l, r < n). Изначально оба они указывают на первый элемент массива (l = r = 0). Оба указателя могут двигаться только вправо, на одну позицию за раз. При этом указатель l никогда не оказывается правее указателя r, и ни один из них не выходит за пределы массива. Вам нужно после каждого перемещения указателя определить максимум всех элементов от указателя l вправо до указателя r (включая позиции, на которые указывают l и r).

Указание. Учетная стоимость обработки каждого запроса на перемещение и подсчет максимума должна оказаться O(1).
Например:
10
1 4 2 3 5 8 6 7 9 10
12
R R L R R R L L L R L L
Ответ
4 4 4 4 5 8 8 8 8 8 8 6

Решение:
Существует знаменитый алгоритм, который называется невозрастающая очередь.
Суть алгоритма такая - мы должны поддерживать очередь dq в которой будет находиться невозрастающие числа на отрезке [l, r].

Рассмотрим на примере выше, чтобы лучше понять как работает очередь.
В первый момент времени l = r = 0 и dq = {1}.

Передвигаем правый указатель и получаем l = 0, r = 1 должны добавить число 4 в очередь. Удалим с конца все числа которые небольше числа 4 и получаем dq = {4}.

Передвигаем правый указатель и получаем l = 0, r = 2 так как число a[r] = 2 меньше чем 4 то мы просто добавим это число в очередь и получим dq = {4, 2}.

Передвигаем левый указатель и получим l = 1, r = 2. Когда сдвигается левый указатель - это означает, что мы должны удалить все числа слева которые < a[l]. В этом случае не удаляем ничего так как 4 > a[l] = 1.

Передвигаем правый указатель и получим l = 1, r = 3, наша очередь станет равно dq = {4, 3}.

Передвигаем правый указатель и получим l = 1, r = 4, наша очередь станет равно dq = {5}.

Передвигаем правый указатель и получим l = 1, r = 5, наша очередь станет равно dq = {8}
И так далее.

Самое главное поддерживать инвариант - в очереди числа идут по убывания. Все числа в очереди - это подпоследовательность чисел на отрезке [l, r].
Ответом после каждого сдвига указателя - это левое число в очереди.


Время работы O(N)