. Nombre maximum de morceaux à trier

769. Max de morceaux à trier

Difficulté :Moyen

Sujets :Array, Stack, Greedy, Tri, Monotonic Stack

Vous recevez un tableau d'entiers arr de longueur n qui représente une permutation des entiers dans la plage [0, n - 1].

Nous divisons arr en un certain nombre de morceaux (c'est-à-dire des partitions) et trions individuellement chaque morceau. Après les avoir concaténés, le résultat devrait être égal au tableau trié.

Renvoyer le plus grand nombre de morceaux que nous pouvons créer pour trier le tableau.

Exemple 1 :

• Entrée : arr = [4,3,2,1,0]
• Sortie : 1
• Explication :
  • La division en deux morceaux ou plus ne renverra pas le résultat requis.
  • Par exemple, diviser en [4, 3], [2, 1, 0] donnera [3, 4, 0, 1, 2], qui n'est pas trié.

Exemple 2 :

• Entrée : arr = [1,0,2,3,4]
• Sortie : 4
• Explication :
  • Nous pouvons diviser en deux morceaux, tels que [1, 0], [2, 3, 4].
  • Cependant, la division en [1, 0], [2], [3], [4] est le plus grand nombre de morceaux possible.

Contraintes :

• n == arr.length
• 1 <= n <= 10
• 0 <= arr[i] < n
• Tous les éléments de l'arr sont uniques.

Indice :

1. Le premier morceau peut être trouvé comme le plus petit k pour lequel A[:k 1] == [0, 1, 2, ...k]; puis nous répétons ce processus.

Solution :

Nous devons trouver le plus grand nombre de morceaux pouvant être formés de telle sorte que chaque morceau puisse être trié individuellement, et une fois concaténé, le résultat est la version triée de l'ensemble du tableau.

Approche:

1. Observation clé :

   • Le tableau est une permutation d'entiers de 0 à n-1. L'idée est de parcourir le tableau et de trouver des positions où les morceaux peuvent être séparés.
   • Un morceau peut être trié si, pour tous les indices du morceau, l'élément maximum jusqu'à ce point ne dépasse pas l'élément minimum après ce point dans le tableau trié d'origine.

2. Stratégie :

   • Suivez la valeur maximale rencontrée lors de votre déplacement de gauche à droite.
   • A chaque index i, vérifiez si la valeur maximale jusqu'à i est inférieure ou égale à i. Si cette condition est remplie, cela signifie que vous pouvez diviser le tableau à cet index car la partie gauche peut être triée indépendamment.

3. Étapes :

   • Parcourez le tableau tout en conservant le maximum d'exécution.
   • Chaque fois que le maximum courant est égal à l'index actuel, un morceau peut être créé.
   • Comptez le nombre de ces morceaux.

Implémentons cette solution en PHP : 769. Max de morceaux à trier

  
  
  Explication:




Initialisation :


Nous commençons par maxSoFar = -1 pour nous assurer que nous suivons correctement la valeur maximale dans le tableau lorsque nous le parcourons.

chunks = 0 garde une trace du nombre de morceaux qui peuvent être formés.



Boucle :


Nous parcourons chaque élément du tableau.
Pour chaque élément, nous mettons à jour le maxSoFar pour qu'il soit la valeur maximale entre l'élément actuel et le maximum vu précédemment.
Si maxSoFar == i, cela signifie que le tableau jusqu'à l'index i peut être trié indépendamment et qu'il s'agit d'un morceau valide.
Nous incrémentons le nombre de morceaux chaque fois que cette condition est vraie.



Retour :


Enfin, le nombre total de morceaux est renvoyé.





  
  
  Complexité temporelle :




Complexité temporelle : O(n), où n est la longueur du tableau. Nous effectuons un seul passage à travers le tableau.

Complexité spatiale : O(1), car nous n'utilisons que quelques variables pour stocker les résultats intermédiaires.



  
  
  Exemple de procédure pas à pas :


Pour arr = [1, 0, 2, 3, 4] :


À l'indice 0, la valeur maximale rencontrée jusqu'à présent est 1. On ne peut pas diviser ici.
À l'index 1, la valeur maximale est 1, ce qui correspond à l'index 1 actuel, nous pouvons donc le diviser en un morceau.
À l'index 2, la valeur maximale est 2, et elle correspond à l'index 2, donc nous nous séparons à nouveau.
À l'indice 3, la valeur maximale est 3, et elle correspond à l'indice 3, donc nous nous séparons à nouveau.
À l'index 4, la valeur maximale est 4, et elle correspond à l'index 4, donc nous nous séparons à nouveau.


Ainsi, le résultat pour ce cas est 4 car nous pouvons le diviser en 4 morceaux.

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!