Finden Sie die Leistung von K-Size-Subarrays I

3254. Finden Sie die Leistungsfähigkeit von K-Size-Subarrays I

Schwierigkeit:Mittel

Themen:Array, Schiebefenster

Sie erhalten ein Array von ganzen Zahlen der Länge n und einer positiven ganzen Zahl k.

Die Leistung eines Arrays ist definiert als:

• Sein maximales Element, wenn alle seine Elemente aufeinanderfolgende sind und in aufsteigender Reihenfolge sortiert sind.
• -1 sonst.

Sie müssen die Potenz aller Subarrays¹ von Zahlen der Größe k ermitteln.

Gibt ein ganzzahliges Array-Ergebnisse der Größe n - k 1 zurück, wobei results[i] die Potenz von nums[i..(i k - 1)] ist.

Beispiel 1:

• Eingabe: nums = [1,2,3,4,3,2,5], k = 3
• Ausgabe: [3,4,-1,-1,-1]
• Erklärung: Es gibt 5 Unterarrays mit Zahlen der Größe 3:
  • [1, 2, 3] mit dem maximalen Element 3.
  • [2, 3, 4] mit dem maximalen Element 4.
  • [3, 4, 3], deren Elemente nicht aufeinanderfolgend sind.
  • [4, 3, 2], deren Elemente nicht sortiert sind.
  • [3, 2, 5], deren Elemente nicht aufeinanderfolgend sind.

Beispiel 2:

• Eingabe: nums = [2,2,2,2,2], k = 4
• Ausgabe: [-1,-1]

Beispiel 3:

• Eingabe: nums = [3,2,3,2,3,2], k = 2
• Ausgabe: [-1,3,-1,3,-1]

Einschränkungen:

• 1 <= n == nums.length <= 500
• 1 <= nums[i] <= 10⁵
• 1 <= k <= n

Hinweis:

1. Können wir eine Brute-Force-Lösung mit verschachtelten Schleifen und HashSet verwenden?

Lösung:

Wir können die Aufgabe wie folgt unterteilen:

Problemaufschlüsselung:

1. Wir erhalten ein Array nums der Länge n und eine positive ganze Zahl k. Wir müssen alle Subarrays der Größe k berücksichtigen und ihre Leistung berechnen.
2. Die Leistung eines Subarrays ist:
   • Das maximale Element des Subarrays, wenn alle Elemente aufeinanderfolgende sind und in aufsteigender Reihenfolge sortiert sind.
   • -1 sonst.
3. Wir müssen ein Array der Größe n - k 1 zurückgeben, wobei jedes Element der Potenz des jeweiligen Unterarrays entspricht.

Planen:

1. Schiebefenster-Ansatz: Wir gleiten über das Array und überprüfen jedes Unterarray der Länge k.
2. Überprüfen Sie, ob das Subarray sortiert ist: Wir müssen prüfen, ob das Subarray aufeinander folgende und in aufsteigender Reihenfolge sortierte Elemente enthält.
3. Maximum oder -1 zurückgeben: Wenn das Subarray gültig ist, geben wir das maximale Element zurück. Andernfalls geben Sie -1 zurück.

Schritte:

1. Überprüfen Sie, ob das Subarray sortiert ist:
   • Ein sortiertes Subarray mit aufeinanderfolgenden Elementen sollte die Eigenschaft haben: nums[i 1] - nums[i] == 1 für jedes i im Subarray.
2. Schiebefenster:
   • Überprüfen Sie für jedes Unterarray der Länge k, ob es sortiert ist, und geben Sie das maximale Element zurück, falls gültig, andernfalls geben Sie -1 zurück.

Lassen Sie uns diese Lösung in PHP implementieren: 3254. Finden Sie die Leistungsfähigkeit von K-Size-Subarrays I

  
  
  Erläuterung:




Schiebefenster: Wir verwenden eine for-Schleife von i = 0 bis i = n – k, um alle Subarrays der Größe k zu berücksichtigen. Für jedes Subarray verwenden wir array_slice(), um das Subarray zu extrahieren.

Sortierungsprüfung: Für jedes Subarray prüfen wir, ob es mit aufeinanderfolgenden Elementen sortiert ist, indem wir das Subarray durchlaufen und prüfen, ob jedes Paar aufeinanderfolgender Elemente eine Differenz von 1 aufweist.

Ergebnis: Wenn das Subarray gültig ist, hängen wir den Maximalwert des Subarrays an das Ergebnis an. Ansonsten hängen wir -1 an.



  
  
  Zeitkomplexität:



Wir iterieren über n - k 1 Subarrays.
Für jedes Subarray prüfen wir, ob die Elemente aufeinanderfolgend sind, was O(k) Zeit dauert.
Die Gesamtzeitkomplexität beträgt also O((n - k 1) * k), was sich zu O(n * k) vereinfacht.



  
  
  Überlegungen zum Randfall:



Wenn k = 1, ist jedes Subarray trivial sortiert (es enthält nur ein Element), und die Potenz jedes Subarrays ist das Element selbst.
Wenn das Subarray nicht fortlaufend ist, wird sofort -1 zurückgegeben.



  
  
  Beispielausgaben:



Für nums = [1, 2, 3, 4, 3, 2, 5], k = 3, ist die Ausgabe [3, 4, -1, -1, -1].
Für nums = [2, 2, 2, 2, 2], k = 4 ist die Ausgabe [-1, -1].
Für nums = [3, 2, 3, 2, 3, 2], k = 2 ist die Ausgabe [-1, 3, -1, 3, -1].


Diese Lösung sollte effizient für die Problembeschränkungen funktionieren.

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








Subarray: Ein Subarray ist eine zusammenhängende, nicht leere Folge von Elementen innerhalb eines Arrays. ↩





          

            
  

            
        
Das obige ist der detaillierte Inhalt vonFinden Sie die Leistung von K-Size-Subarrays I. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!