. Maximaler Abstand in Arrays

624. Maximaler Abstand in Arrays

Schwierigkeit:Mittel

Themen:Array, Greedy

Sie erhalten m Arrays, wobei jedes Array in aufsteigender Reihenfolge sortiert ist.

Sie können zwei Ganzzahlen aus zwei verschiedenen Arrays (jedes Array wählt eine aus) auswählen und den Abstand berechnen. Wir definieren den Abstand zwischen zwei ganzen Zahlen a und b als ihre absolute Differenz |a - b|.

Gib die maximale Entfernung zurück.

Beispiel 1:

• Eingabe: arrays = [[1,2,3],[4,5],[1,2,3]]
• Ausgabe: 4
• Erklärung: Eine Möglichkeit, den maximalen Abstand 4 zu erreichen, besteht darin, 1 im ersten oder dritten Array auszuwählen und 5 im zweiten Array auszuwählen.

Beispiel 2:

• Eingabe: arrays = [[1],[1]]
• Ausgabe: 0

Einschränkungen:

• m == arrays.length
• 2 <= m <= 10⁵
• 1 <= arrays[i].length <= 500
• -10⁴ <= arrays[i][j] <= 10⁴
• arrays[i] wird in aufsteigender Reihenfolge sortiert.
• Es werden höchstens 10⁵Ganzzahlen in allen Arrays vorhanden sein.

Lösung:

Wir müssen den maximal möglichen Abstand zwischen zwei ganzen Zahlen berechnen, die jeweils aus unterschiedlichen Arrays ausgewählt werden. Die wichtigste Beobachtung ist, dass der maximale Abstand höchstwahrscheinlich zwischen dem Minimalwert eines Arrays und dem Maximalwert eines anderen Arrays liegt.

Um dieses Problem zu lösen, können wir die folgenden Schritte ausführen:

1. Verfolgen Sie den Mindest- und Höchstwert, während Sie die Arrays durchlaufen.
2. Berechnen Sie für jedes Array den potenziellen maximalen Abstand, indem Sie das Minimum des aktuellen Arrays mit dem globalen Maximum und das Maximum des aktuellen Arrays mit dem globalen Minimum vergleichen.
3. Aktualisieren Sie das globale Minimum und Maximum, während Sie fortfahren.

Lassen Sie uns diese Lösung in PHP implementieren: 624. Maximaler Abstand in Arrays

  
  
  Erläuterung:




min_value und max_value werden mit den Minimal- und Maximalwerten des ersten Arrays initialisiert.
Während wir jedes Array beginnend mit dem zweiten durchlaufen:


Wir berechnen den Abstand, indem wir das globale Minimum mit dem Maximum des aktuellen Arrays und das globale Maximum mit dem Minimum des aktuellen Arrays vergleichen.
Aktualisieren Sie die max_distance, wenn eine größere Entfernung gefunden wird.
Aktualisieren Sie min_value und max_value, um die bisher gefundenen Mindest- und Höchstwerte widerzuspiegeln.





Abschließend gibt die Funktion die maximal gefundene Entfernung zurück.



Diese Lösung läuft in O(m)-Zeit, wobei m die Anzahl der Arrays ist, was sie angesichts der Problembeschränkungen effizient macht.

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. Maximaler Abstand in Arrays. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!