Kürzestes Subarray, das entfernt werden muss, um das Array zu sortieren

1574. Kürzestes Subarray, das entfernt werden muss, um das Array zu sortieren

Schwierigkeit:Mittel

Themen:Array, Zwei Zeiger, Binäre Suche, Stapel, Monotoner Stapel

Entfernen Sie bei einem gegebenen ganzzahligen Array arr ein Unterarray (kann leer sein) aus arr, sodass die verbleibenden Elemente in arr nicht abnehmend sind.

Gibt die Länge des kürzesten zu entfernenden Subarrays zurück.

Ein Subarray ist eine zusammenhängende Teilsequenz des Arrays.

Beispiel 1:

• Eingabe: arr = [1,2,3,10,4,2,3,5]
• Ausgabe: 3
• Erklärung: Das kürzeste Subarray, das wir entfernen können, ist [10,4,2] mit der Länge 3. Die verbleibenden Elemente danach sind [1,2,3,3,5] und werden sortiert.
  • Eine andere richtige Lösung besteht darin, das Subarray [3,10,4] zu entfernen.

Beispiel 2:

• Eingabe: arr = [5,4,3,2,1]
• Ausgabe: 4
• Erklärung: Da das Array streng abnehmend ist, können wir nur ein einzelnes Element behalten. Daher müssen wir ein Unterarray der Länge 4 entfernen, entweder [5,4,3,2] oder [4,3,2,1].

Beispiel 3:

• Eingabe: arr = [1,2,3]
• Ausgabe: 0
• Erklärung: Das Array nimmt bereits nicht ab. Wir müssen keine Elemente entfernen.

Einschränkungen:

• 1 <= arr.length <= 10⁵
• 0 <= arr[i] <= 10⁹

Hinweis:

1. Der Schlüssel besteht darin, das längste nicht abnehmende Subarray zu finden, das mit dem ersten Element beginnt bzw. mit dem letzten Element endet.
2. Nach dem Entfernen eines Teilarrays ist das Ergebnis die Verkettung eines sortierten Präfixes und eines sortierten Suffixes, wobei das letzte Element des Präfixes kleiner als das erste Element des Suffixes ist.

Lösung:

Wir können Sortier- und binäre Suchtechniken verwenden. Hier ist der Plan:

Ansatz:

1. Zwei-Punkte-Ansatz:

   • Identifizieren Sie zunächst das längste nicht abnehmende Präfix (linker Zeiger).
   • Identifizieren Sie dann das längste nicht abnehmende Suffix (rechter Zeiger).
   • Versuchen Sie danach, diese beiden Subarrays zu kombinieren, indem Sie den mittleren Teil des Arrays berücksichtigen und das zu entfernende Subarray so anpassen, dass das kombinierte Array nicht abnimmt.

2. Monotoner Stapel:

   • Verwenden Sie einen monotonen Stapel, um Subarray-Elemente sortiert zu verwalten.

3. Schritte:

   • Finden Sie das längste nicht abnehmende Präfix (links).
   • Finden Sie das längste nicht abnehmende Suffix (rechts).
   • Versuchen Sie, die beiden Subarrays zusammenzuführen, indem Sie nach Elementen suchen, die eine gültige Kombination bilden können.

4. Optimierung:

   • Verwenden Sie die binäre Suche, um den Zusammenführungsschritt zu optimieren und das kleinste zu entfernende Subarray zu finden.

Lassen Sie uns diese Lösung in PHP implementieren: 1574. Kürzestes Subarray, das entfernt werden muss, um das Array zu sortieren

  
  
  Erläuterung:




Längstes nicht abnehmendes Präfix und Suffix:


Das Präfix wird bestimmt, indem das Array vom Anfang an durchlaufen wird, bis die Elemente in nicht absteigender Reihenfolge vorliegen.
In ähnlicher Weise wird das Suffix durch Durchlaufen vom Ende bestimmt.



Anfängliche Mindestentfernung:


Berechnen Sie die Entfernungslänge, indem Sie nur das Präfix oder das Suffix beibehalten.



Präfix und Suffix zusammenführen:


Verwenden Sie zwei Zeiger (i für Präfix und j für Suffix), um das kleinste zu entfernende Subarray zu finden, sodass das letzte Element des Präfixes kleiner oder gleich dem ersten Element des Suffixes ist.



Ergebnis zurückgeben:


Das Ergebnis ist die Mindestlänge des zu entfernenden Subarrays, berechnet als der kleinere Wert aus der anfänglichen Entfernung oder der Zusammenführung von Präfix und Suffix.





  
  
  Komplexität




Zeitkomplexität: O(n), da das Array höchstens zweimal durchlaufen wird.

Raumkomplexität: O(1), da nur wenige Variablen verwendet werden.


Diese Lösung findet effizient das kürzeste zu entfernende Subarray, um das Array mithilfe einer Zwei-Zeiger-Technik zu sortieren, und verarbeitet große Arrays bis zur Einschränkung von 10^5 Elementen.

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 vonKürzestes Subarray, das entfernt werden muss, um das Array zu sortieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!