. Maximaler Abstand in Arrays

624. Maximaler Abstand in Arrays

Schwierigkeit:Mittel

Themen:Array, Greedy

Sie erhalten m Arrays, wobei jedes Array inaufsteigender Reihenfolge.

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

Zurückdie maximale Distanz.

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] ist inaufsteigender Reihenfolge.
sortiert
• In allen Arrays gibt es höchstens 10⁵Ganzzahlen.

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_valueundmax_valuewerden 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.
          
         
Schließlich 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, demRepositoryeinen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Eure 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!