Тихая улица по датчикам

В городе вдоль одной длинной улицы стоят датчики шума — по одному на каждый квартал. Диспетчер хочет найти самый длинный непрерывный отрезок кварталов, где шум «примерно одинаковый»: разница между самым громким и самым тихим кварталом на этом отрезке не превышает K.

Нужно узнать длину такого самого длинного отрезка.

Важно: значения могут не помещаться в 32-битный тип (как на олимпиадах), используйте 64-битные целые. В Python это не проблема.

Формат ввода

• В первой строке два целых числа n и K.
• Во второй строке n целых чисел a1, a2, ..., an — уровень шума по кварталам.

Формат вывода Выведите одно целое число — максимальную длину непрерывного отрезка, на котором max(a[l..r]) - min(a[l..r]) <= K.

Ограничения

• 1 <= n <= 20000
• 0 <= K <= 10^6
• 0 <= ai <= 10^6

Пример Ввод:

7 3
1 3 6 7 9 2 4

Вывод:

3

Ключевое наблюдение: нам нужен самый длинный отрезок, где max - min <= K. Если фиксировать правую границу r и увеличивать её слева направо, то левую границу l можно двигать только вправо (никогда не назад): как только окно стало «шумным» (условие нарушилось), его можно исправить только сдвигом l.

Проблема: быстро знать max и min на текущем окне. Пересчитывать их каждый раз за O(n) нельзя. Решение — две монотонные очереди (deque) с индексами:

• maxdq хранит кандидатов на максимум по убыванию значений.
• mindq хранит кандидатов на минимум по возрастанию значений.

В голове очереди всегда стоит индекс текущего max/min.

План:

• Идём r = 0..n-1.
• Добавляем r в maxdq, выкидывая с конца все индексы с a[idx] <= a[r].
• Аналогично добавляем r в mindq, выкидывая с конца все индексы с a[idx] >= a[r].
• Пока a[maxdq[0]] - a[mindq[0]] > K, двигаем l вправо; если голова какой-то очереди равна старому l, удаляем её.
• После этого окно валидно, обновляем ответ длиной r - l + 1.

Мини-сниппет проверки окна: while a[maxdq[0]] - a[mindq[0]] > K: ...

Сложность: O(n), потому что каждый индекс добавляется и удаляется из каждой очереди не больше одного раза.

Частая ошибка: хранить в deque сами значения, а не индексы — тогда невозможно понять, «вышел» ли элемент за левую границу, и очереди начнут врать.