Ctrl K

Ровный участок забора

Средняя
Высоты столбиков забора записаны в массиве heights (высоты отсчитываются от некоторого уровня и могут быть отрицательными). За один шаг можно увеличить или уменьшить высоту любого столбика на 1. Нужно, чтобы где-то в заборе нашлись width подряд стоящих столбиков одинаковой высоты. Верните наименьшее число шагов, за которое этого можно добиться.
Пример 1
heights=[5, 1, 4, 2, 9], width=3 → 3

Возьмём отрезок [1, 4, 2] и выровняем всё под 2: 1 шаг для первого столбика и 2 для второго — итого 3. Другие отрезки дороже.

Пример 2
heights=[-3, 7, 7, 0], width=2 → 0

Два соседних столбика по 7 уже одной высоты.

Пример 3
heights=[0, 10, -10], width=3 → 20
Ограничения
  • 2 ≤ len(heights) ≤ 10⁵
  • -10⁶ ≤ heights[i] ≤ 10⁶
  • 2 ≤ width ≤ len(heights)
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиОтрезки с k нечётными СредняяМедиана в скользящем окне СложнаяСамый узкий отрезок для всех списков СложнаяДешёвая нарезка с близкими началами СложнаяСуммы самых частых в окне Лёгкая
загружаем Python…
Вход
heights=[5, 1, 4, 2, 9], width=3
Ожидается
3

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