heights из положительных чисел и бюджет budget. Возьмём любой непрерывный отрезок массива. За одну операцию можно увеличить на 1 любой его элемент; разрешено сделать не больше budget операций.
Отрезок подходит, если такими операциями его можно сделать неубывающим (каждый элемент не меньше предыдущего). Каждый отрезок рассматривается отдельно: изменения в одном не влияют на другие.
Верните количество подходящих отрезков.heights=[4, 2, 5, 1], budget=3 → 7
Всего 10 отрезков. Не получится поправить только [5, 1] (нужно 4), [2, 5, 1] (нужно 4) и [4, 2, 5, 1] (нужно 2 + 4 = 6). Ответ 10 − 3 = 7.
heights=[1, 2, 3], budget=1 → 6
Массив уже не убывает, так что подходят все 6 отрезков.
heights=[9, 1, 1], budget=8 → 5
Отрезок [9, 1, 1] стоит 8 + 8 = 16 и не подходит, остальные 5 отрезков укладываются в бюджет.
heights=[4, 2, 5, 1], budget=3
7
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 135 тестов на сервере, включая скрытые.