Problem
Ein Zug erhöht einen Wert im Array um 1. Mache das Array nicht abnehmend: Jeder Wert muss größer oder gleich dem unmittelbar davorstehenden Wert sein. Du darfst keine Werte verringern oder die Reihenfolge ändern.
Implementiere increasing_array(numbers).
Eingabe
numbers: Die Werte in ihrer ursprünglichen Reihenfolge.
Ausgabe
Gib die minimale Gesamtanzahl an Erhöhungen um eins zurück.
Einschränkungen
1 ≤ Länge ≤ 200.000. Jeder Wert liegt zwischen 1 und 1.000.000.000. Verwende ein vorzeichenbehaftetes 64-Bit-Ergebnis.
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
Erhöhe 1 auf 4 mit drei Zügen und 3 auf 4 mit einem Zug. Das Ergebnis [4, 4, 4] benötigt insgesamt vier Züge.
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
Jeder Wert ist bereits mindestens so groß wie der vorherige; gleiche Nachbarn sind erlaubt.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Gehe von links nach rechts, weil jeder Wert nur vom vorherigen abhängt.
Hinweis 2
Wenn ein Wert zu klein ist, erhöhe ihn gerade so weit, dass er dem laufenden Mindestwert entspricht.
Hinweis 3
Verfolge die Gesamtzahl der Erhöhungen genau, denn frühere Anpassungen beeinflussen spätere Vergleiche.
Erwartete Komplexität
Zeit O(n), zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.