Mindestanzahl an Entfernungen, um ein Gebirgsmassiv zu erstellen

1671. Mindestanzahl an Entfernungen, um ein Gebirgsmassiv zu erstellen

Schwierigkeit:Schwer

Themen:Array, Binäre Suche, Dynamische Programmierung, Greedy

Sie erinnern sich vielleicht, dass ein Array-Array genau dann ein Berg-Array ist, wenn:

• arr.length >= 3
• Es gibt einen Index i (0-indexiert) mit 0 < ich < arr.length - 1 so dass:
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i 1] > ... > arr[arr.length - 1]

  Geben Sie bei einem gegebenen ganzzahligen Array nums die Mindestanzahl der zu entfernenden Elemente zurück, um nums zu einem Bergarray zu machen.

  Beispiel 1:

  • Eingabe: nums = [1,3,1]
  • Ausgabe: 0
  • Erklärung: Das Array selbst ist ein Berg-Array, daher müssen wir keine Elemente entfernen.

  Beispiel 2:

  • Eingabe: nums = [2,1,1,5,6,2,3,1]
  • Ausgabe: 3
  • Erklärung: Eine Lösung besteht darin, die Elemente bei den Indizes 0, 1 und 5 zu entfernen, sodass die Array-Nummern = [1,5,6,3,1] sind.

  Einschränkungen:

  • 3 <= nums.length <= 1000
  • 1 <= nums[i] <= 10⁹
  • Es ist garantiert, dass Sie aus Zahlen ein Gebirgsmassiv machen können.

  Hinweis:

  1. Denken Sie anstelle minimaler Elemente in die entgegengesetzte Richtung, um die maximale Bergteilfolge zu entfernen
  2. Denken Sie an LIS, es ist irgendwie nah dran

  Lösung:

  Wir können einen dynamischen Programmieransatz mit der Idee verwenden, die maximale Bergteilsequenz zu finden, anstatt die zu entfernenden Elemente direkt zu zählen. Dieser Ansatz basiert auf der Suche nach zwei Longest Increasing Subsequences (LIS) für jede Position im Array: eine geht von links nach rechts und die andere geht von rechts nach links. Sobald wir die längste mögliche Berg-Teilsequenz haben, gibt uns die Differenz zwischen der ursprünglichen Array-Länge und dieser Teilsequenz-Länge die minimal zu entfernenden Elemente.

  Lösungsübersicht

  1. Identifizieren Sie zunehmende Teilsequenzlängen:

     • Berechnen Sie das leftLIS-Array, wobei leftLIS[i] die Länge der am längsten ansteigenden Teilsequenz darstellt, die bei i endet (von links nach rechts).

  2. Identifizieren Sie abnehmende Teilsequenzlängen:

     • Berechnen Sie das rightLIS-Array, wobei rightLIS[i] die Länge der längsten abnehmenden Teilsequenz darstellt, beginnend bei i (von rechts nach links).

  3. Maximale Berglänge berechnen:

     • Für jeden Index i mit 0 < ich < n - 1, prüfen Sie, ob ein gültiger Peak vorhanden ist (d. h. leftLIS[i] > 1 und rightLIS[i] > 1). Berechnen Sie die Berglänge bei i als leftLIS[i] rightLIS[i] - 1.

  4. Erhalten Sie die Mindestentfernungen:

     • Die minimal zu entfernenden Elemente sind die ursprüngliche Array-Länge minus der längsten gefundenen Berglänge.

  Lassen Sie uns diese Lösung in PHP implementieren: 1671. Mindestanzahl an Entfernungen, um ein Gebirgsmassiv zu erstellen
  

  <?php
  /**
   * @param Integer[] $nums
   * @return Integer
   */
  function minimumMountainRemovals($nums) {
      ...
      ...
      ...
      /**
       * go to ./solution.php
       */
  }
  
  // Example usage
  $nums1 = [1, 3, 1];
  echo minimumMountainRemovals($nums1); // Output: 0
  
  $nums2 = [2, 1, 1, 5, 6, 2, 3, 1];
  echo minimumMountainRemovals($nums2); // Output: 3
  ?>
  

  Erläuterung:

  1. Linke LIS-Berechnung:

     • leftLIS[i] speichert die maximale Länge einer aufsteigenden Teilsequenz, die bei i endet. Wir durchlaufen jedes i und iterieren für jedes i von 0 bis i-1, um die längste Teilsequenz zu finden, die bei i endet.

  2. Richtige LIS-Berechnung:

     • rightLIS[i] speichert die maximale Länge einer abnehmenden Teilsequenz beginnend bei i. Wir iterieren rückwärts von n-2 bis 0 und für jedes i von n-1 bis i 1, um die längste Teilsequenz zu finden, die bei i beginnt.

  3. Bergberechnung:

     • Ein gültiger Peak am Index i muss vorhanden sein leftLIS[i] > 1 und rightLIS[i] > 1. Die Länge eines Berges mit Gipfel bei i ist leftLIS[i] rightLIS[i] - 1.

  4. Endgültige Berechnung:

     • Die minimal erforderlichen Entfernungen sind die Differenz zwischen der ursprünglichen Array-Länge und der maximal gefundenen Berglänge.

  Komplexitätsanalyse

  • Zeitkomplexität: O(n²), aufgrund der Doppelschleife in den LIS-Berechnungen.
  • Raumkomplexität: O(n), zum Speichern der leftLIS- und rightLIS-Arrays.

  Diese Lösung stellt sicher, dass wir die maximale Gebirgsteilfolge finden und die minimalen Entfernungen berechnen, die erforderlich sind, um eine Gebirgsgruppe zu erreichen.

  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 vonMindestanzahl an Entfernungen, um ein Gebirgsmassiv zu erstellen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!