Nombre minimum de suppressions pour créer un tableau de montagne

1671. Nombre minimum de suppressions pour créer un tableau de montagne

Difficulté : Difficile

Sujets :Array, recherche binaire, programmation dynamique, gourmand

Vous vous souvenez peut-être qu'un tableau arr est un tableau de montagne si et seulement si :

• arr.length >= 3
• Il existe un index i (0-indexé) avec 0 < je &Lt ; arr.length - 1 tel que :
  • arr[0] < arr[1] ≪ ... ≪ arr[je - 1] &Lt ; arr[i]
  • arr[i]> arr[je 1] > ...> arr[arr.longueur - 1]

  Étant donné un tableau entier nums, renvoie le nombre minimum d'éléments à supprimer pour faire de nums un tableau de montagne.

  Exemple 1 :

  • Entrée : nums = [1,3,1]
  • Sortie : 0
  • Explication : Le tableau lui-même est un tableau de montagnes, nous n'avons donc pas besoin de supprimer aucun élément.

  Exemple 2 :

  • Entrée : nums = [2,1,1,5,6,2,3,1]
  • Sortie : 3
  • Explication : Une solution consiste à supprimer les éléments aux indices 0, 1 et 5, ce qui rend le tableau nums = [1,5,6,3,1].

  Contraintes :

  • 3 <= nums.length <= 1000
  • 1 <= nums[i] <= 10⁹
  • Il est garanti que vous pouvez créer un réseau de montagnes à partir de chiffres.

  Indice :

  1. Pensez dans la direction opposée au lieu d'éléments minimum pour supprimer la sous-séquence maximale de montagne
  2. Pensez à LIS, c'est un peu proche

  Solution :

  Nous pouvons utiliser une approche de programmation dynamique avec l'idée de trouver la sous-séquence maximale de montagne plutôt que de compter directement les éléments à supprimer. Cette approche est basée sur la recherche de deux Sous-séquences croissantes les plus longues (LIS) pour chaque position du tableau : l'une allant de gauche à droite et l'autre allant de droite à- à gauche. Une fois que nous aurons la sous-séquence de montagne la plus longue possible, la différence entre la longueur du tableau d'origine et cette longueur de sous-séquence nous donnera le minimum d'éléments à supprimer.

  Aperçu de la solution

  1. Identifier les longueurs de sous-séquences croissantes :

     • Calculez le tableau leftLIS, où leftLIS[i] représente la longueur de la sous-séquence croissante la plus longue se terminant par i (allant de gauche à droite).

  2. Identifier les longueurs de sous-séquences décroissantes :

     • Calculez le tableau rightLIS, où rightLIS[i] représente la longueur de la sous-séquence décroissante la plus longue commençant à i (allant de droite à gauche).

  3. Calculer la longueur maximale de la montagne :

     • Pour chaque index i où 0 < je &Lt ; n - 1, vérifiez s'il existe un pic valide (c'est-à-dire leftLIS[i] > 1 et rightLIS[i] > 1). Calculez la longueur de la montagne en i comme leftLIS[i] rightLIS[i] - 1.

  4. Obtenez le minimum de suppressions :

     • Les éléments minimum à supprimer seront la longueur originale du tableau moins la longueur de montagne la plus longue trouvée.

  Implémentons cette solution en PHP : 1671. Nombre minimum de retraits pour réaliser un tableau de montagne
  

  <?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
  ?>
  

  Explication:

  1. Calcul LIS gauche :

     • leftLIS[i] stocke la longueur maximale d'une sous-séquence croissante se terminant par i. Nous parcourons chaque i, et pour chaque i, parcourons de 0 à i-1 pour trouver la sous-séquence la plus longue se terminant par i.

  2. Calcul LIS droit :

     • rightLIS[i] stocke la longueur maximale d'une sous-séquence décroissante commençant à i. Nous parcourons en arrière de n-2 à 0, et pour chaque i, parcourons de n-1 jusqu'à i 1 pour trouver la sous-séquence la plus longue commençant à i.

  3. Calcul de la montagne :

     • Un pic valide à l'index que je dois avoir laisséLIS[i] > 1 et rightLIS[i] > 1. La longueur d'une montagne dont le sommet est en i est leftLIS[i] rightLIS[i] - 1.

  4. Calcul final :

     • Les suppressions minimales nécessaires sont la différence entre la longueur originale du tableau et la longueur maximale de la montagne trouvée.

  Analyse de complexité

  • Complexité temporelle : O(n²), en raison de la double boucle dans les calculs LIS.
  • Complexité spatiale : O(n), pour stocker les tableaux leftLIS et rightLIS.

  Cette solution garantit que nous trouvons la sous-séquence de montagnes maximale et calculons les suppressions minimales requises pour obtenir un réseau de montagnes.

  Liens de contact

  Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

  Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

  • LinkedIn
  • GitHub

  Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!