Минимальное увеличение / уменьшение, чтобы массив не увеличивался

Учитывая массив a, ваша задача - преобразовать его в невозрастающую форму, чтобы мы могли либо увеличивать, либо уменьшать значение массива на 1 с минимально возможными изменениями.

Примеры :

 Ввод: a [] = {3, 1, 2, 1}
Выход: 1
Объяснение :
Мы можем преобразовать массив в 3 1 1 1 с помощью
изменение 3-го элемента массива, т.е. 2 
в предыдущее целое число 1 за один шаг
следовательно, требуется только один шаг.

Ввод: a [] = {3, 1, 5, 1}
Выход: 4
Нам нужно уменьшить 5 до 1, чтобы массив был отсортирован
в невозрастающем порядке.

Ввод: a [] = {1, 5, 5, 5}
Выход: 4
Нам нужно увеличить 1 до 5.

Подход грубой силы: мы рассматриваем обе возможности для каждого элемента и находим как минимум две возможности.

Эффективный подход: рассчитайте сумму абсолютных разностей между конечными элементами массива и текущими элементами массива. Таким образом, ответ будет суммой разницы между i-м элементом и наименьшим элементом, имевшим место до этого момента. Для этого мы можем поддерживать минимальную кучу, чтобы найти наименьший элемент, встречающийся до этого момента. В очередь с минимальным приоритетом мы поместим элементы, и новые элементы будут сравниваться с предыдущим минимумом. Если будет найден новый минимум, мы обновим его, это будет сделано, потому что каждый следующий элемент должен быть меньше, чем текущий минимальный элемент, найденный до сих пор. Здесь мы вычисляем разницу, чтобы получить, насколько нам нужно изменить текущее число, чтобы оно было равно или меньше предыдущих чисел, встреченных до. Наконец, сумма всех этих различий будет нашим ответом, поскольку это даст окончательное значение, до которого мы должны изменить элементы.

Ниже представлена реализация описанного выше подхода:

Сложность времени: O (n log (n))
Космическая сложность: O (n)
См. Также: Преобразование в строго возрастающий массив с минимальными изменениями.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.