. Max. Brocken zum Sortieren

769. Max. Brocken zum Sortieren

Schwierigkeit:Mittel

Themen: Array, Stack, Greedy, Sortieren, Monotoner Stack

Sie erhalten ein ganzzahliges Array arr der Länge n, das eine Permutation der ganzen Zahlen im Bereich [0, n - 1] darstellt.

Wir teilen arr in eine Anzahl von Chunks (d. h. Partitionen) auf und sortieren jeden Chunk einzeln. Nach der Verkettung sollte das Ergebnis dem sortierten Array entsprechen.

Gib die größte Anzahl an Blöcken zurück, die wir zum Sortieren des Arrays erstellen können.

Beispiel 1:

• Eingabe: arr = [4,3,2,1,0]
• Ausgabe: 1
• Erklärung:
  • Eine Aufteilung in zwei oder mehr Teile führt nicht zum gewünschten Ergebnis.
  • Zum Beispiel führt die Aufteilung in [4, 3], [2, 1, 0] zu [3, 4, 0, 1, 2], was nicht sortiert ist.

Beispiel 2:

• Eingabe: arr = [1,0,2,3,4]
• Ausgabe: 4
• Erklärung:
  • Wir können in zwei Teile aufteilen, z. B. [1, 0], [2, 3, 4].
  • Die Aufteilung in [1, 0], [2], [3], [4] ist jedoch die höchstmögliche Anzahl an Blöcken.

Einschränkungen:

• n == arr.length
• 1 <= n <= 10
• 0 <= arr[i] < n
• Alle Elemente von arr sind einzigartig.

Hinweis:

1. Der erste Block kann als das kleinste k gefunden werden, für das A[:k 1] == [0, 1, 2, ...k]; dann wiederholen wir diesen Vorgang.

Lösung:

Wir müssen die größte Anzahl von Blöcken finden, die gebildet werden können, sodass jeder Block einzeln sortiert werden kann. Bei der Verkettung ist das Ergebnis die sortierte Version des gesamten Arrays.

Ansatz:

1. Wichtige Beobachtung:

   • Das Array ist eine Permutation von ganzen Zahlen von 0 bis n-1. Die Idee besteht darin, das Array zu durchqueren und Positionen zu finden, an denen die Blöcke getrennt werden können.
   • Ein Block kann sortiert werden, wenn für alle Indizes innerhalb des Blocks das maximale Element bis zu diesem Punkt das minimale Element nach diesem Punkt im ursprünglichen sortierten Array nicht überschreitet.

2. Strategie:

   • Verfolgen Sie den Maximalwert, der bei der Bewegung von links nach rechts auftritt.
   • Überprüfen Sie bei jedem Index i, ob der Maximalwert bis i kleiner oder gleich i ist. Wenn diese Bedingung zutrifft, bedeutet dies, dass Sie das Array an diesem Index teilen können, da der linke Teil unabhängig sortiert werden kann.

3. Schritte:

   • Iterieren Sie über das Array und behalten Sie dabei das laufende Maximum bei.
   • Immer wenn das laufende Maximum dem aktuellen Index entspricht, kann ein Block erstellt werden.
   • Zählen Sie die Anzahl solcher Brocken.

Lassen Sie uns diese Lösung in PHP implementieren: 769. Max. Stücke zum Sortieren

  
  
  Erläuterung:




Initialisierung:


Wir beginnen mit maxSoFar = -1, um sicherzustellen, dass wir den Maximalwert im Array beim Durchlaufen korrekt verfolgen.

chunks = 0 verfolgt die Anzahl der Chunks, die gebildet werden können.



Schleife:


Wir durchlaufen jedes Element im Array.
Für jedes Element aktualisieren wir maxSoFar so, dass es der Maximalwert zwischen dem aktuellen Element und dem zuvor gesehenen Maximum ist.
Wenn maxSoFar == i, bedeutet dies, dass das Array bis zum Index i unabhängig sortiert werden kann und dies ein gültiger Block ist.
Wir erhöhen die Chunk-Anzahl jedes Mal, wenn diese Bedingung zutrifft.



Rückgabe:


Schließlich wird die Gesamtzahl der Chunks zurückgegeben.





  
  
  Zeitkomplexität:




Zeitkomplexität: O(n), wobei n die Länge des Arrays ist. Wir durchlaufen das Array nur einmal.

Raumkomplexität: O(1), da wir nur wenige Variablen zum Speichern von Zwischenergebnissen verwenden.



  
  
  Beispielhafte Vorgehensweise:


Für arr = [1, 0, 2, 3, 4]:


Bei Index 0 ist der bisher gefundene Maximalwert 1. Wir können hier nicht aufteilen.
Bei Index 1 ist der Maximalwert 1, was dem aktuellen Index 1 entspricht, sodass wir ihn in einen Block aufteilen können.
Bei Index 2 ist der Maximalwert 2 und er stimmt mit Index 2 überein, also teilen wir erneut auf.
Bei Index 3 ist der Maximalwert 3 und er stimmt mit Index 3 überein, also teilen wir erneut auf.
Bei Index 4 ist der Maximalwert 4 und er stimmt mit Index 4 überein, also teilen wir erneut auf.


Die Ausgabe für diesen Fall beträgt also 4, da wir sie in 4 Teile aufteilen können.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:


LinkedIn
GitHub



          

            
  

            
        
Das obige ist der detaillierte Inhalt von. Max. Brocken zum Sortieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!