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.
Einschränkungen
1 ≤ length ≤ 200,000. Each value is between 1 and 1,000,000,000. Use a signed 64-bit result.
Beispiele
Eingabe:
numbers = [4, 1, 3]
Erwartete Ausgabe:
expected = 4Eingabe:
std::vector<long long> numbers = {4, 1, 3};
Erwartete Ausgabe:
long long expected = 4;Eingabe:
long[] numbers = new long[] {4, 1, 3};
Erwartete Ausgabe:
long expected = 4;Erläuterung
Raise 1 to 4 using three moves and 3 to 4 using one move. The result [4, 4, 4] uses four moves.
Eingabe:
numbers = [1, 2, 2, 5]
Erwartete Ausgabe:
expected = 0Eingabe:
std::vector<long long> numbers = {1, 2, 2, 5};
Erwartete Ausgabe:
long long expected = 0;Eingabe:
long[] numbers = new long[] {1, 2, 2, 5};
Erwartete Ausgabe:
long expected = 0;Erläuterung
Every value is already at least the preceding value; equal neighbors are allowed.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Scan from left to right, because each value only depends on the previous one.
Hinweis 2
Whenever a value is too small, raise it just enough to match the running minimum allowed value.
Hinweis 3
Track the total increments carefully, since earlier increases affect later comparisons.
Erwartete Komplexität
O(n) time, O(1) extra space
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.