Ctrl K

Разрывы по всем окнам

Сложная
Для массива чисел назовём **разрывом** место в его отсортированной копии, где соседние элементы отличаются больше чем на 1. Например, у [5, 1, 3, 3] отсортированная копия [1, 3, 3, 5], и в ней два разрыва: между 1 и 3 и между 3 и 5. Дан массив values. Посчитайте число разрывов для каждого его непрерывного непустого подмассива (окна) и верните сумму этих чисел.
Пример 1
values=[3, 1, 4, 2] → 5

По одному разрыву в окнах [3, 1], [1, 4], [4, 2], [3, 1, 4] и [1, 4, 2]. В одиночных окнах и во всём массиве [1, 2, 3, 4] разрывов нет. Итого 5.

Пример 2
values=[2, 2, 4, 4] → 4

Разрыв между 2 и 4 есть в каждом окне, где встречаются обе цифры: [2, 4], [2, 4, 4], [2, 2, 4], [2, 2, 4, 4]. Повторы разрывов не создают.

Пример 3
values=[1, 1, 1] → 0
Ограничения
  • 1 ≤ len(values) ≤ 1000
  • 1 ≤ values[i] ≤ len(values)
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСколько цветёт в день визита СложнаяПодъём по строкам и столбцам СложнаяТабло заказов для кухни СредняяСводка по двум складам ЛёгкаяСамый ходовой остаток на складе Средняя
загружаем Python…
Вход
values=[3, 1, 4, 2]
Ожидается
5

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