Задача Яндекса.

Дается массив a из целых положительных чисел, а также число k. Найти максимальный по длине подотрезок в котором разница между максимальным и минимальным элементом будет не больше k.

Решение:
Наум, конечно, приходит два указателя. Это, кстати, хорошая идея.

И так, думаем в сторону двух указателей. Всё по шаблону, перебираем правый край отрезка 0 <= r < n, для каждого такого r будем искать оптимальный l, в котором разница максимального и минимального элемента не больше k.
Можно легко понять, что для каждого следующего r его оптимальный l будет не левее чем l для r - 1.

Осталось только быстро находить минимум и максимум на отрезке... Да, конечно, можно попытаться написать дерево отрезков, что позволит вам находить мин/макс за логарифм, но, к сожалению, задачу так не засчитают, нужно научиться за константу находить.

Для тех, кто не знал, можно с помощью монотонного стека находить мин/макс на отрезке, а в этой задаче нам понадобятся два монотонных стека, один для минимума, другой для максимума. Вот пример.

И так для решения - этой задачи нужно было хранить два стека. (ГПТ кстати хорошо решает такую задачу :))

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

Код в комментариях: