Ctrl K

Ближайшие разные значения на отрезках

Средняя
Дан массив values из целых чисел от 1 до 100 и список запросов ranges, где ranges[i] = [lo, hi]. Для каждого запроса рассмотрите отрезок массива с индекса lo по индекс hi включительно и найдите наименьшую разницу |a - b| среди пар его элементов с **разными** значениями. Если все элементы отрезка равны (в том числе если он состоит из одного элемента), ответ на запрос — -1. Верните массив ответов в порядке запросов.
Пример 1
values=[6, 2, 9, 2, 5], ranges=[[0, 1], [1, 3], [2, 4], [0, 4]] → [4, 7, 3, 1]

[6, 2] → 4; [2, 9, 2] → 7 (две двойки равны и не считаются); [9, 2, 5] → 3; во всём массиве ближе всего 5 и 6 → 1.

Пример 2
values=[3, 3, 3], ranges=[[0, 2], [1, 2]] → [-1, -1]

Все числа одинаковые, различных пар нет — в обоих ответах -1.

Ограничения
  • 2 ≤ len(values) ≤ 10⁵
  • 1 ≤ values[i] ≤ 100
  • 1 ≤ len(ranges) ≤ 2 · 10⁴
  • 0 ≤ lo ≤ hi < len(values)
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСудоку без конфликтов СредняяРазложить анаграммы по группам СредняяНулевые кресты СредняяДерево по прямому и симметричному обходам СредняяДерево по симметричному и обратному обходам Средняя
загружаем Python…
Вход
values=[6, 2, 9, 2, 5], ranges=[[0, 1], [1, 3], [2, 4], [0, 4]]
Ожидается
[4, 7, 3, 1]

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 89 тестов на сервере, включая скрытые.