Le sous-tableau le plus court à supprimer pour trier le tableau

1574. Le sous-tableau le plus court à supprimer pour trier le tableau

Difficulté :Moyen

Sujets : Tableau, deux pointeurs, recherche binaire, pile, pile monotone

Étant donné un tableau d'entiers arr, supprimez un sous-tableau (peut être vide) de arr de telle sorte que les éléments restants dans arr soient non décroissants.

Renvoyer la longueur du sous-tableau le plus court à supprimer.

Un sous-tableau est une sous-séquence contiguë du tableau.

Exemple 1 :

• Entrée : arr = [1,2,3,10,4,2,3,5]
• Sortie : 3
• Explication : Le sous-tableau le plus court que nous pouvons supprimer est [10,4,2] de longueur 3. Les éléments restants après cela seront [1,2,3,3,5] qui sont triés.
  • Une autre solution correcte consiste à supprimer le sous-tableau [3,10,4].

Exemple 2 :

• Entrée : arr = [5,4,3,2,1]
• Sortie : 4
• Explication : Le tableau étant strictement décroissant, on ne peut conserver qu'un seul élément. Par conséquent, nous devons supprimer un sous-tableau de longueur 4, soit [5,4,3,2], soit [4,3,2,1].

Exemple 3 :

• Entrée : arr = [1,2,3]
• Sortie : 0
• Explication : Le tableau est déjà non décroissant. Nous n'avons besoin de supprimer aucun élément.

Contraintes :

• 1 <= longueur arr. <= 10⁵
• 0 <= arr[i] <= 10⁹

Indice :

1. La clé est de trouver le sous-tableau non décroissant le plus long commençant respectivement par le premier élément ou se terminant par le dernier élément.
2. Après avoir supprimé un sous-tableau, le résultat est la concaténation d'un préfixe trié et d'un suffixe trié, où le dernier élément du préfixe est plus petit que le premier élément du suffixe.

Solution :

Nous pouvons utiliser des techniques de tri et de recherche binaire. Voici le plan :

Approche:

1. Approche à deux indicateurs :

   • Tout d'abord, identifiez le préfixe non décroissant le plus long (pointeur gauche).
   • Ensuite, identifiez le suffixe non décroissant le plus long (pointeur droit).
   • Après cela, essayez de combiner ces deux sous-tableaux en considérant la partie médiane du tableau et en ajustant le sous-tableau à supprimer de telle manière que le tableau combiné ne soit pas décroissant.

2. Pile monotone :

   • Utilisez une pile monotone pour vous aider à gérer les éléments du sous-tableau de manière triée.

3. Étapes :

   • Trouvez le préfixe non décroissant le plus long (à gauche).
   • Trouvez le suffixe non décroissant le plus long (à droite).
   • Essayez de fusionner les deux sous-tableaux en recherchant des éléments pouvant former une combinaison valide.

4. Optimisation :

   • Utilisez la recherche binaire pour optimiser l'étape de fusion afin de trouver le plus petit sous-tableau à supprimer.

Implémentons cette solution en PHP : 1574. Le sous-tableau le plus court à supprimer pour trier le tableau

  
  
  Explication:




Préfixe et suffixe non décroissants les plus longs :


Le préfixe est déterminé en parcourant le tableau depuis le début jusqu'à ce que les éléments soient dans un ordre non décroissant.
De même, le suffixe est déterminé en parcourant depuis la fin.



Suppression minimale initiale :


Calculez la longueur de suppression en ne gardant que le préfixe ou le suffixe.



Fusion du préfixe et du suffixe :


Utilisez deux pointeurs (i pour préfixe et j pour suffixe) pour trouver le plus petit sous-tableau à supprimer de telle sorte que le dernier élément du préfixe soit inférieur ou égal au premier élément du suffixe.



Résultat du retour :


Le résultat est la longueur minimale du sous-tableau à supprimer, calculée comme la plus petite entre la suppression initiale ou la fusion du préfixe et du suffixe.





  
  
  Complexité




Complexité temporelle : O(n), car le tableau est parcouru au plus deux fois.

Complexité spatiale : O(1), car seules quelques variables sont utilisées.


Cette solution trouve efficacement le sous-tableau le plus court à supprimer pour trier le tableau en utilisant une technique à deux pointeurs, et elle gère de grands tableaux jusqu'à la contrainte de 10^5 éléments.

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!