Ctrl K

Подъём отрезками

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

Поднимаем все четыре столбика на 1, затем столбики 0–1 ещё на 1, затем столбик 1 дважды и столбик 3 дважды: 1 + 1 + 2 + 2 = 6.

Пример 2
heights=[5, 5, 5] → 5

Пять раз поднимаем весь ряд целиком.

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

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