Problem
One move increases one array value by 1. Make the array nondecreasing: each value must be greater than or equal to the one immediately before it. You may not decrease values or reorder them.
Implement increasing_array(numbers).
Input
numbers: The values in their original order.
Output
Return the minimum total number of unit increments.
Constraints
1 ≤ length ≤ 200,000. Each value is between 1 and 1,000,000,000. Use a signed 64-bit result.
Examples
Input:
numbers = [4, 1, 3]
Expected output:
expected = 4Input:
std::vector<long long> numbers = {4, 1, 3};
Expected output:
long long expected = 4;Input:
long[] numbers = new long[] {4, 1, 3};
Expected output:
long expected = 4;Explanation
Raise 1 to 4 using three moves and 3 to 4 using one move. The result [4, 4, 4] uses four moves.
Input:
numbers = [1, 2, 2, 5]
Expected output:
expected = 0Input:
std::vector<long long> numbers = {1, 2, 2, 5};
Expected output:
long long expected = 0;Input:
long[] numbers = new long[] {1, 2, 2, 5};
Expected output:
long expected = 0;Explanation
Every value is already at least the preceding value; equal neighbors are allowed.
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
Scan from left to right, because each value only depends on the previous one.
Hint 2
Whenever a value is too small, raise it just enough to match the running minimum allowed value.
Hint 3
Track the total increments carefully, since earlier increases affect later comparisons.
Expected complexity
O(n) time, O(1) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.