Finden Sie ein Gebäude, in dem sich Alice und Bob treffen können

2940. Finden Sie ein Gebäude, in dem sich Alice und Bob treffen können

Schwierigkeit:Schwer

Themen: Array, Binäre Suche, Stapel, Binärer indizierter Baum, Segmentbaum, Heap (Prioritätswarteschlange), Monotoner Stapel

Sie erhalten ein 0-indiziertes Array mit Höhen positiver Ganzzahlen, wobei heights[i] die Höhe des i^ten Gebäudes darstellt.

Wenn sich eine Person in Gebäude i befindet, kann sie genau dann in jedes andere Gebäude j umziehen, wenn i < j und heights[i] < heights[j].

Sie erhalten außerdem weitere Array-Abfragen, bei denen query[i] = [a_i, b_i] ist. Bei der i^ten Abfrage ist Alice dabei, ein_i zu bauen, während Bob dabei ist, b_i zu bauen.

Gibt ein Array ans zurück, wobei ans[i] der Index des Gebäudes ganz links ist, in dem sich Alice und Bob bei der i^ten-Abfrage treffen können. Wenn Alice und Bob bei Abfrage i nicht in ein gemeinsames Gebäude umziehen können, setzen Sie ans[i] auf -1.

Beispiel 1:

• Eingabe: Höhen = [6,4,8,5,2,7], Abfragen = [[0,1],[0,3],[2,4],[3,4] ,[2,2]]
• Ausgabe: [2,5,-1,5,2]
• Erklärung: In der ersten Abfrage können Alice und Bob in Gebäude 2 umziehen, da heights[0] < heights[2] und heights[1] < Höhen[2].
  • In der zweiten Abfrage können Alice und Bob in Gebäude 5 umziehen, da heights[0] < heights[5] und heights[3] < Höhen[5].
  • Bei der dritten Abfrage kann Alice Bob nicht treffen, da Alice nicht in ein anderes Gebäude umziehen kann.
  • In der vierten Abfrage können Alice und Bob in Gebäude 5 umziehen, da heights[3] < heights[5] und heights[4] < Höhen[5].
  • Bei der fünften Abfrage befinden sich Alice und Bob bereits im selben Gebäude.
  • Für ans[i] != -1 kann gezeigt werden, dass ans[i] das Gebäude ganz links ist, in dem Alice und Bob sich treffen können.
  • Für ans[i] == -1 kann gezeigt werden, dass es kein Gebäude gibt, in dem Alice und Bob sich treffen können.

Beispiel 2:

• Eingabe: heights = [5,3,8,2,6,1,4,6], querys = [[0,7],[3,5],[5,2],[ 3,0],[1,6]]
• Ausgabe: [7,6,-1,4,6]
• Erklärung: In der ersten Abfrage kann Alice direkt zu Bobs Gebäude ziehen, da heights[0] < Höhen[7].
  • In der zweiten Abfrage können Alice und Bob in Gebäude 6 umziehen, da heights[3] < heights[6] und heights[5] < Höhen[6].
  • Bei der dritten Abfrage kann Alice Bob nicht treffen, da Bob nicht in ein anderes Gebäude umziehen kann.
  • In der vierten Abfrage können Alice und Bob in Gebäude 4 umziehen, da heights[3] < heights[4] und heights[0] < Höhen[4].
  • In der fünften Abfrage kann Alice direkt zu Bobs Gebäude ziehen, da heights[1] < Höhen[6].
  • Für ans[i] != -1 kann gezeigt werden, dass ans[i] das Gebäude ganz links ist, in dem Alice und Bob sich treffen können.
  • Für ans[i] == -1 kann gezeigt werden, dass es kein Gebäude gibt, in dem Alice und Bob sich treffen können.

Einschränkungen:

• 1 <= heights.length <= 5 * 10⁴
• 1 <= heights[i] <= 10⁹
• 1 <= query.length <= 5 * 10⁴
• Abfragen[i] = [a_i, b_i]
• 0 <= a_i, b_i <= heights.length - 1

Hinweis:

1. Für jede Abfrage [x, y], wenn x > y, vertausche x und y. Nun können wir davon ausgehen, dass x <= y.
2. Für jede Abfrage [x, y], wenn x == y oder heights[x] < heights[y], dann ist die Antwort y, da x ≤ y.
3. Andernfalls müssen wir den kleinsten Index t finden, sodass y < t und heights[x] < Höhen[t]. Beachten Sie, dass heights[y] <= heights[x], also heights[x] < heights[t] ist eine ausreichende Bedingung.
4. Um den Index t für jede Abfrage zu finden, sortieren Sie die Abfragen in absteigender Reihenfolge von y. Durchlaufen Sie die Abfragen und behalten Sie dabei einen monotonen Stapel bei, den wir binär durchsuchen können, um den Index t zu finden.

Lösung:

Das Problem besteht darin, das Gebäude ganz links zu bestimmen, in dem Alice und Bob sich angesichts ihrer Startgebäude und Bewegungsregeln treffen können. Bei jeder Abfrage geht es darum, einen Treffpunkt anhand der Gebäudehöhe zu finden. Dies ist aufgrund der Bewegungseinschränkungen und der Notwendigkeit einer effizienten Berechnung eine Herausforderung.

Wichtige Punkte

1. Alice und Bob können in ein anderes Gebäude umziehen, wenn dessen Höhe unbedingt höher ist als die des aktuellen Gebäudes.
2. Suchen Sie für jede Abfrage den gültigen Treffpunkt ganz links oder geben Sie -1 zurück, wenn kein solches Gebäude vorhanden ist.
3. Die Einschränkungen erfordern eine Lösung, die besser ist als ein naiver O(n²)-Ansatz.

Anfahrt

1. Beobachtungen:

   • Wenn a == b, sind Alice und Bob bereits im selben Gebäude.
   • Wenn heights[a] < heights[b], Bobs Gebäude ist der Treffpunkt.
   • Andernfalls finden Sie den kleinsten Gebäudeindex t > b wobei:
     • Höhen[a] < heights[t]
     • heights[b] <= heights[t] (da b im Höhenvergleich bereits kleiner als a ist).

2. Optimierung mit monotonem Stapel:

   • Ein monotoner Stapel hilft dabei, die gültigen Gebäude, zu denen Alice und Bob ziehen können, effizient zu verfolgen. Gebäude werden dem Stapel so hinzugefügt, dass sichergestellt wird, dass die Höhen in absteigender Reihenfolge vorliegen, was eine schnelle binäre Suche ermöglicht.

3. Abfragesortierung:

   • Sortieren Sie die Abfragen in absteigender Reihenfolge von b, um zuerst Gebäude mit größeren Indizes zu verarbeiten. Dies stellt sicher, dass wir den Stapel effizient aufbauen, wenn wir von höheren zu niedrigeren Indizes wechseln.

4. Binäre Suche auf Stack:

   • Verwenden Sie für jede Abfrage die binäre Suche auf dem monotonen Stapel, um den kleinsten Index t zu finden, der die Bedingungen erfüllt.

Planen

1. Sortieren Sie Abfragen basierend auf dem größeren der beiden Indizes (b) in absteigender Reihenfolge.
2. Durchlaufen Sie das Array rückwärts und behalten Sie dabei einen monotonen Stapel gültiger Indizes bei.
3. Überprüfen Sie für jede Abfrage triviale Fälle (a == b oder heights[a] < heights[b]).
4. In nicht trivialen Fällen verwenden Sie den Stapel, um das am weitesten links stehende gültige Gebäude über die binäre Suche zu finden.
5. Gibt die Ergebnisse in der ursprünglichen Abfragereihenfolge zurück.

Lösungsschritte

1. Abfragen vorverarbeiten:

   • Stellen Sie aus Konsistenzgründen in jeder Abfrage ein <= b sicher.
   • Abfragen nach b in absteigender Reihenfolge sortieren.

2. Durch Abfragen iterieren:

   • Behalten Sie einen monotonen Stapel bei, während wir das Array durchlaufen.
   • Für jede Abfrage:
     • Wenn a == b, lautet die Antwort b.
     • Wenn heights[a] < heights[b], die Antwort ist b.
     • Andernfalls verwenden Sie den Stapel, um den kleinsten gültigen Index t > zu finden. b.

   • Binäre Suche auf Stack:

     • Verwenden Sie die binäre Suche, um schnell den kleinsten Index t auf dem Stapel zu finden, der heights[t] > erfüllt. Höhen[a].

   • Ursprüngliche Bestellung wiederherstellen:

     • Ergebnisse wieder den ursprünglichen Abfrageindizes zuordnen.

   • Ergebnisse zurückgeben.

   Lassen Sie uns diese Lösung in PHP implementieren: 2940. Finden Sie ein Gebäude, in dem sich Alice und Bob treffen können
   

   <?php
   /**
    * @param Integer[] $heights
    * @param Integer[][] $queries
    * @return Integer[]
    */
   function leftmostBuildingQueries($heights, $queries) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
   }
   
   /**
    * @param $queries
    * @return array
    */
   private function getIndexedQueries($queries) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
   }
   
   /**
    * @param $stack
    * @param $a
    * @param $heights
    * @return mixed|null
    */
   private function findUpperBound($stack, $a, $heights) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
   }
   
   class IndexedQuery {
       public $queryIndex;
       public $a; // Alice's index
       public $b; // Bob's index
   
       /**
        * @param $queryIndex
        * @param $a
        * @param $b
        */
       public function __construct($queryIndex, $a, $b) {
           $this->queryIndex = $queryIndex;
           $this->a = $a;
           $this->b = $b;
       }
   }
   
   // Test the function
   $heights = [6, 4, 8, 5, 2, 7];
   $queries = [[0, 1], [0, 3], [2, 4], [3, 4], [2, 2]];
   print_r(leftmostBuildingQueries($heights, $queries));
   
   $heights = [5, 3, 8, 2, 6, 1, 4, 6];
   $queries = [[0, 7], [3, 5], [5, 2], [3, 0], [1, 6]];
   print_r(leftmostBuildingQueries($heights, $queries));
   ?>
   

   Erläuterung:

   1. Abfragen sortieren: Die Abfragen werden in absteigender Reihenfolge nach b sortiert, um größere Indizes zuerst zu verarbeiten, was uns ermöglicht, unseren monotonen Stapel während der Verarbeitung zu aktualisieren.
   2. Monotonischer Stapel: Der Stapel wird verwendet, um den Überblick über die Erstellung von Indizes zu behalten, in denen Alice und Bob zusammentreffen können. Wir behalten nur Gebäude, deren Höhe größer ist als alle zuvor gesehenen Gebäude im Stapel.
   3. Binäre Suche: Bei der Beantwortung jeder Anfrage verwenden wir die binäre Suche, um effizient den kleinsten Index t zu finden, bei dem die Bedingungen erfüllt sind.

   Beispiel-Anleitung

   Eingang:

   • Höhen = [6,4,8,5,2,7]
   • Abfragen = [[0,1],[0,3],[2,4],[3,4],[2,2]]

   Verfahren:

   1. Abfragen sortieren:

      • Indizierte Abfragen: [(2,4), (3,4), (0,3), (0,1), (2,2)]

   2. Monotonen Stapel erstellen:

      • Beginnen Sie beim höchsten Index und fügen Sie Indizes zum Stapel hinzu:
        • Bei Index 5: Stack = [5]
        • Bei Index 4: Stack = [5, 4]
        • ...

   3. Abfrageverarbeitung:

      • Für Abfrage [0,1], heights[0] < heights[1]: Ergebnis = 2.
      • ...

   Ausgabe:

   [2, 5, -1, 5, 2]

   Zeitkomplexität

   1. Abfragesortierung: O(Q log Q), wobei Q die Anzahl der Abfragen ist.
   2. Monotone Stapelkonstruktion: O(N), wobei N die Länge der Höhen ist.
   3. Binäre Suche für jede Abfrage: O(Q log N).

   Insgesamt: O(N Q log (Q N)).

   Ausgabe als Beispiel

   Eingabe:
   

   $heights = [6, 4, 8, 5, 2, 7];
   $queries = [[0, 1], [0, 3], [2, 4], [3, 4], [2, 2]];
   

   Ausgabe:
   

   print_r(findBuilding($heights, $queries)); // [2, 5, -1, 5, 2]
   

   Dieser Ansatz bewältigt große Einschränkungen effizient, indem er einen monotonen Stapel und eine binäre Suche nutzt. Es gewährleistet eine optimale Abfrageverarbeitung bei gleichzeitiger Wahrung der Korrektheit.

   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 vonFinden Sie ein Gebäude, in dem sich Alice und Bob treffen können. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!