. Rampe mit maximaler Breite

962. Rampe mit maximaler Breite

Schwierigkeit:Mittel

Themen:Array, Stapel, monotoner Stapel

Eine Rampe in einem ganzzahligen Array nums ist ein Paar (i, j), für das i < j und nums[i] <= nums[j]. Die Breite einer solchen Rampe beträgt j - i.

Geben Sie bei einem gegebenen Ganzzahl-Array Nums die maximale Breite einer Rampe in Nums zurück. Wenn es in Zahlen keine Rampe gibt, geben Sie 0 zurück.

Beispiel 1:

• Eingabe: nums = [6,0,8,2,1,5]
• Ausgabe: 4
• Erklärung: Die maximale Breitenrampe wird bei (i, j) = (1, 5) erreicht: nums[1] = 0 und nums[5] = 5.

Beispiel 2:

• Eingabe: nums = [9,8,1,0,1,9,4,0,4,1]
• Ausgabe: 7
• Erklärung: Die maximale Breitenrampe wird bei (i, j) = (2, 9) erreicht: nums[2] = 1 und nums[9] = 1.

Einschränkungen:

• 2 <= nums.length <= 5 * 10⁴
• 0 <= nums[i] <= 5 * 10⁴

Lösung:

Wir können das Konzept eines monotonen Stapels nutzen. Hier ist die Lösung und Erklärung:

Ansatz:

1. Monotonisch abnehmender Stapel: Wir erstellen einen Stapel, der die Indizes der Elemente so verfolgt, dass nums[stack[i]] in absteigender Reihenfolge vorliegt. Dadurch können wir später Paare (i, j) finden, bei denen nums[i] <= nums[j].
ist
2. Vom Ende aus durchlaufen: Nachdem wir den Stapel erstellt haben, durchlaufen wir das Array vom Ende (j von n-1 bis 0), um zu versuchen, das am weitesten entfernte i für jedes j zu finden, wobei nums[i] <= nums[j].
3. Aktualisieren Sie die maximale Breite: Immer wenn nums[i] <= nums[j] für die aktuelle Oberseite des Stapels gilt, berechnen Sie die Rampenbreite j - i und aktualisieren Sie die maximale Breite, wenn sie größer ist.

Lassen Sie uns diese Lösung in PHP implementieren: 962. Rampe mit maximaler Breite

  
  
  Erläuterung:




Erstellen Sie einen abnehmenden Stapel:


Durchlaufen Sie das Array und fügen Sie Indizes zum Stapel hinzu.
Fügen Sie einen Index nur hinzu, wenn er einem Wert entspricht, der kleiner oder gleich dem Wert des letzten Index im Stapel ist. Dadurch wird sichergestellt, dass die Werte im Stapel in absteigender Reihenfolge vorliegen.



Überquerung vom Ende:


Wenn wir das Array rückwärts durchgehen, entfernen Sie für jedes j die Indizes i vom Stapel, solange nums[i] <= nums[j] ist.
Berechnen Sie die Breite j - i und aktualisieren Sie maxWidth.



Warum das funktioniert:


Durch die Aufrechterhaltung eines abnehmenden Indexstapels stellen wir sicher, dass wir, wenn wir auf ein j mit einem größeren Wert stoßen, eine größere Breite j - i erhalten können, wenn i vom Stapel entfernt wird.



Zeitkomplexität:


Der Aufbau des Stapels dauert O(n) Zeit, da jeder Index einmal gepusht wird.
Das Durchlaufen der End- und Popup-Indizes erfordert ebenfalls O(n), da jeder Index höchstens einmal gepoppt wird.
Insgesamt läuft die Lösung in O(n)-Zeit, was für Eingabegrößen bis zu 5 * 10^4 effizient ist.





  
  
  Ausgabe:



Für nums = [6, 0, 8, 2, 1, 5] ist die Ausgabe 4, entsprechend der Rampe (1, 5).
Für nums = [9, 8, 1, 0, 1, 9, 4, 0, 4, 1] ist die Ausgabe 7, entsprechend der Rampe (2, 9).


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. Rampe mit maximaler Breite. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!