Минимизируйте операции приращения, чтобы сделать массив неубывающим

Дан массив arr[] из n целых чисел. Измените массив так, чтобы каждый элемент был не меньше предыдущего элемента. Это можно сделать, увеличив значение любого элемента на 1 . Задача состоит в том, чтобы найти минимальное количество ходов, необходимое для того, чтобы массив стал неубывающим.

Примеры:

Input: n = 5, arr[] = {8, 9, 2, 7, 7}
Output: 11
Explanation: The array should be modified to 8 9 9 9 9, this can be done by 11 moves(7 + 2 + 2).

Input: n = 10, arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Output: 0
Explanation: The array is already non decreasing.

Подход: Идея состоит в том, чтобы пройтись по массиву и в любой момент, когда текущий элемент меньше предыдущего, затем сделать текущий как предыдущий и увеличить счет. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную count как 0 , чтобы сохранить результат.
• Перебрать диапазон [0, n), используя переменную i , и выполнить следующие задачи:
  • Если arr[i] меньше, чем arr[i-1] , тогда установите значение arr[i] как arr[i-1] и увеличьте значение count на arr[i]-arr[i-1].
• После выполнения вышеуказанных шагов выведите значение count в качестве ответа.

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

Временная сложность: O(N)
Вспомогательное пространство: O(1)