Least Total Change to Make an Array Monotonic
Problem statement
You are given an integer array nums. You may change any number to any other integer. Changing a number from x to y costs |x - y|, and the total change is the sum of these costs.
Return the smallest total change that makes the array either non-decreasing (every number is at least the one before it) or non-increasing (every number is at most the one before it). Equal neighbors are allowed in both. You may pick whichever of the two is cheaper.
Function
minimumTotalChange(nums: int[]) → longExamples
Example 1
nums = [0,1,2,5,6,5,7]return = 1Change the 5 at index 5 to 6. The array becomes [0, 1, 2, 5, 6, 6, 7], which never goes down. The total change is 6 - 5 = 1. The array is not already sorted either way, so the answer cannot be 0. The answer is 1.
Example 2
nums = [9,8,7,2,3,3]return = 1Change the 2 at index 3 to 3. The array becomes [9, 8, 7, 3, 3, 3], which never goes up. The total change is 3 - 2 = 1. The answer is 1.
Example 3
nums = [1,10,2,3]return = 8To make it never go down, lower the 10 to 2: [1, 2, 2, 3] with total change 8. Raising the 2 and the 3 to 10 instead would cost 8 + 7 = 15. Making it never go up costs at least 10, for example [10, 10, 2, 2], which changes the 1 by 9 and the 3 by 1. So the answer is 8.
Constraints
1 <= nums.length <= 10000 <= nums[i] <= 10^9