Сделать массив великим
Условие
Массив великий, если в каждом его подмассиве длины 3 есть элемент не меньше k. Разрешена одна операция: увеличить любой элемент на единицу. Верни минимальное число операций.
Примеры
makeGreat([3, 2, 0, 1, 1, 4], 4) // 4
makeGreat([5, 0, 2, 0, 0, 6], 4) // 2
makeGreat([5, 0, 0, 0, 0, 6], 4) // 4
Как подойти
Жадность здесь неверна: локально дешевле поднять ближайший маленький элемент, но это сдвигает следующую обязательную позицию неудачно. Правильная модель - динамика по позиции последнего «покрывающего» элемента: любые два соседних покрывающих элемента не могут отстоять больше чем на три, иначе между ними найдётся подмассив без большого элемента. Стоимость поднятия считается заранее: max(0, k − x). Улучшение до O(n) - скользящий минимум по окну из трёх значений dp.
Подсказки: 3
- Поднятые элементы должны стоять не дальше чем через два друг от друга.
- dp[i] - минимальная стоимость, если последний поднятый элемент на позиции i.
- В конце ответ - минимум по трём последним позициям.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.