Découvrez la puissance des sous-réseaux de taille K I

3254. Découvrez la puissance des sous-tableaux de taille K I

Difficulté :Moyen

Sujets : Tableau, fenêtre coulissante

Vous recevez un tableau de nombres entiers de longueur n et un positif entier k.

La puissance d'un tableau est définie comme :

• Son élément maximum si tous ses éléments sont consécutifs et triés par ordre croissant.
• -1 sinon.

Vous devez trouver la puissance de tous les sous-tableaux¹ de nombres de taille k.

Renvoyer un tableau d'entiers results de taille n - k 1, où results[i] est la puissance de nums[i..(i k - 1)].

Exemple 1 :

• Entrée : nums = [1,2,3,4,3,2,5], k = 3
• Sortie : [3,4,-1,-1,-1]
• Explication : Il existe 5 sous-tableaux de nombres de taille 3 :
  • [1, 2, 3] avec l'élément maximum 3.
  • [2, 3, 4] avec l'élément maximum 4.
  • [3, 4, 3] dont les éléments ne sont pas consécutifs.
  • [4, 3, 2] dont les éléments ne sont pas triés.
  • [3, 2, 5] dont les éléments ne sont pas consécutifs.

Exemple 2 :

• Entrée : nums = [2,2,2,2,2], k = 4
• Sortie : [-1,-1]

Exemple 3 :

• Entrée : nums = [3,2,3,2,3,2], k = 2
• Sortie : [-1,3,-1,3,-1]

Contraintes :

• 1 <= n == nums.length <= 500
• 1 <= nums[i] <= 10⁵
• 1 <= k <= n

Indice :

1. Pouvons-nous utiliser une solution de force brute avec des boucles imbriquées et HashSet ?

Solution :

On peut décomposer la tâche comme suit :

Répartition du problème :

1. On nous donne un tableau nums de longueur n et un entier positif k. Nous devons considérer tous les sous-tableaux de taille k et calculer leur puissance.
2. La puissance d'un sous-réseau est :
   • L'élément maximum du sous-tableau si tous les éléments sont consécutifs et triés par ordre croissant.
   • -1 sinon.
3. Nous devons renvoyer un tableau de taille n - k 1, où chaque élément correspond à la puissance du sous-tableau respectif.

Plan:

1. Approche par fenêtre coulissante : Nous allons glisser sur le tableau et vérifier chaque sous-tableau de longueur k.
2. Vérifiez si le sous-tableau est trié : Nous devons vérifier si le sous-tableau contient des éléments consécutifs et triés par ordre croissant.
3. Return Maximum ou -1 : Si le sous-tableau est valide, nous renvoyons l'élément maximum. Sinon, retournez -1.

Mesures:

1. Vérifiez si le sous-tableau est trié :
   • Un sous-tableau trié avec des éléments consécutifs doit avoir la propriété : nums[i 1] - nums[i] == 1 pour chaque i dans le sous-tableau.
2. Fenêtre coulissante :
   • Pour chaque sous-tableau de longueur k, vérifiez s'il est trié et renvoyez l'élément maximum s'il est valide, sinon renvoyez -1.

Implémentons cette solution en PHP : 3254. Découvrez la puissance des sous-tableaux de taille K I

  
  
  Explication:




Fenêtre coulissante : Nous utilisons une boucle for de i = 0 à i = n - k pour considérer tous les sous-tableaux de taille k. Pour chaque sous-tableau, nous utilisons array_slice() pour extraire le sous-tableau.

Vérification du tri : Pour chaque sous-tableau, nous vérifions s'il est trié avec des éléments consécutifs en parcourant le sous-tableau et en vérifiant si chaque paire d'éléments consécutifs a une différence de 1.

Résultat : Si le sous-tableau est valide, nous ajoutons la valeur maximale du sous-tableau au résultat. Sinon, on ajoute -1.



  
  
  Complexité temporelle :



Nous parcourons n - k 1 sous-tableaux.
Pour chaque sous-tableau, on vérifie si les éléments sont consécutifs, ce qui prend un temps O(k).
Ainsi, la complexité temporelle globale est O((n - k 1) * k) qui se simplifie en O(n * k).



  
  
  Considérations sur les cas extrêmes :



Si k = 1, chaque sous-tableau est trié de manière triviale (il ne contient qu'un seul élément), et la puissance de chaque sous-tableau sera l'élément lui-même.
Si le sous-tableau n'est pas consécutif, il renverra immédiatement -1.



  
  
  Exemples de sorties :



Pour nums = [1, 2, 3, 4, 3, 2, 5], k = 3, la sortie est [3, 4, -1, -1, -1].
Pour nums = [2, 2, 2, 2, 2], k = 4, la sortie est [-1, -1].
Pour nums = [3, 2, 3, 2, 3, 2], k = 2, la sortie est [-1, 3, -1, 3, -1].


Cette solution devrait fonctionner efficacement pour les contraintes du problème.

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








Sous-tableau : Un sous-tableau est une séquence contiguë non vide d'éléments au sein d'un tableau. ↩





          

            
  

            
        
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!