. Rampe de largeur maximale

962. Rampe de largeur maximale

Difficulté :Moyen

Sujets : Tableau, pile, pile monotone

Une rampe dans un tableau d'entiers nums est une paire (i, j) pour laquelle i < j et nums[i] <= nums[j]. La largeur d'une telle rampe est j - i.

Étant donné un tableau d'entiers nums, renvoie la largeur maximale d'une rampe en nums. S'il n'y a pas de rampe en chiffres, renvoie 0.

Exemple 1 :

• Entrée : nums = [6,0,8,2,1,5]
• Sortie : 4
• Explication : La rampe de largeur maximale est atteinte à (i, j) = (1, 5) : nums[1] = 0 et nums[5] = 5.

Exemple 2 :

• Entrée : nums = [9,8,1,0,1,9,4,0,4,1]
• Sortie :7
• Explication : La rampe de largeur maximale est atteinte à (i, j) = (2, 9) : nums[2] = 1 et nums[9] = 1.

Contraintes :

• 2 <= nums.length <= 5 * 10⁴
• 0 <= nums[i] <= 5 * 10⁴

Solution :

Nous pouvons exploiter le concept de pile monotone. Voici la solution et l'explication :

Approche:

1. Pile décroissante monotone : Nous créons une pile qui garde la trace des indices des éléments de manière à ce que nums[stack[i]] soit dans un ordre décroissant. Cela nous permet de retrouver plus tard des paires (i, j) où nums[i] <= nums[j].
2. Traverse depuis la fin : Après avoir créé la pile, nous parcourons le tableau depuis la fin (j de n-1 à 0) pour essayer de trouver le i le plus éloigné pour chaque j où nums[i] <= nums[j].
3. Mettre à jour la largeur maximale : chaque fois que nums[i] <= nums[j] est valable pour le haut actuel de la pile, calculez la largeur de la rampe j - i et mettez à jour la largeur maximale si elle est plus grande.

Implémentons cette solution en PHP : 962. Rampe de largeur maximale

  
  
  Explication:




Créer une pile décroissante :


Parcourez le tableau et ajoutez des indices à la pile.
Ajoutez un index uniquement s'il correspond à une valeur inférieure ou égale à la valeur du dernier index de la pile. Cela garantit que les valeurs de la pile sont dans un ordre décroissant.



Traverse depuis la fin :


Au fur et à mesure que nous remontons dans le tableau, pour chaque j, extrayons les indices i de la pile tant que nums[i] <= nums[j].
Calculez la largeur j - i et mettez à jour maxWidth.



Pourquoi cela fonctionne :


En maintenant une pile décroissante d'indices, nous garantissons que lorsque nous rencontrons un j avec une valeur plus grande, cela peut nous donner une plus grande largeur j - i lorsque i est retiré de la pile.



Complexité temporelle :


La construction de la pile prend un temps O(n) puisque chaque index est poussé une fois.
Le parcours à partir de la fin et l'affichage des index prennent également O(n) puisque chaque index est affiché au plus une fois.
Dans l'ensemble, la solution s'exécute en temps O(n), ce qui est efficace pour une taille d'entrée allant jusqu'à 5 * 10^4.





  
  
  Sortir:



Pour nums = [6, 0, 8, 2, 1, 5], la sortie est 4, correspondant à la rampe (1, 5).
Pour nums = [9, 8, 1, 0, 1, 9, 4, 0, 4, 1], la sortie est 7, correspondant à la rampe (2, 9).


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!