Sliding Window Maximum
Tu reçois un tableau d’entiers nums et une taille de fenêtre k. Une fenêtre de k valeurs consécutives commence à l’extrémité gauche et se déplace vers la droite d’une position à la fois, jusqu’à ce que son bord droit se trouve sur la dernière valeur. Retourne la plus grande valeur de la fenêtre à chaque position, de gauche à droite : n-k+1 valeurs pour un tableau de longueur n.
Fonction
- numsinteger-array
- le tableau sur lequel glisse la fenêtre
- kinteger
- le nombre de valeurs dans chaque fenêtre
- Renvoieinteger-array
- la valeur la plus élevée de chaque fenêtre, de la fenêtre la plus à gauche à la fenêtre la plus à droite
Contraintes
1 ≤ k ≤ nums.length ≤ 2 × 104-104 ≤ nums[i] ≤ 104- Le résultat contient
nums.length-k+1valeurs, une par fenêtre, de gauche à droite.
Exemples
- Entrée
- nums = [4, 2, 12, 3, 8, 5, 1]k = 3
- Sortie
- [12, 12, 12, 8, 8]
- Explication
- 12 se trouve dans les trois premières fenêtres, donc chacune d’elles renvoie 12. Après sa sortie,
[3, 8, 5]et[8, 5, 1]ont toutes deux 8 comme valeur maximale.
- Entrée
- nums = [-3, -1, -7, -2]k = 2
- Sortie
- [-1, -1, -2]
- Explication
- Les fenêtres sont
[-3, -1],[-1, -7]et[-7, -2]. Le plus grand de deux nombres négatifs est celui qui est le plus proche de zéro, ce qui donne -1, -1 et -2.
- Entrée
- nums = [6, 6, 1]k = 3
- Sortie
- [6]
- Explication
- Lorsque
kest égal à la longueur du tableau, il n’y a qu’une seule fenêtre : le tableau entier. Sa plus grande valeur est 6 ; la deuxième occurrence de 6 ne donne pas une deuxième réponse.
Pour aller plus loin
Peux-tu créer une file qui permet d’ajouter une valeur à la fin, de retirer la valeur au début et de lire son maximum actuel, chacune de ces opérations en temps amorti O(1) ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Parcourir chaque fenêtre pour y trouver sa valeur maximale coûte
kétapes par fenêtre. Compare deux fenêtres voisines : elles partagentk-1valeurs, car une valeur sort à gauche et une autre entre à droite.Lorsqu’une nouvelle valeur entre, toute valeur plus ancienne dans la fenêtre qui est inférieure ou égale à celle-ci ne pourra plus jamais être un maximum. La nouvelle valeur reste dans toutes les fenêtres suivantes qui contiennent encore l’ancienne, et elle est au moins aussi grande. Tu peux définitivement éliminer ces valeurs plus anciennes.
Conservez les indices des valeurs qui subsistent dans une file à double extrémité, avec des valeurs strictement décroissantes de l’avant vers l’arrière. Pour chaque nouvel indice, retirez de l’arrière les valeurs inférieures ou égales, ajoutez l’indice, retirez l’élément en tête s’il est sorti de la fenêtre, puis lisez le maximum de la fenêtre en tête.
Solution
Les fenêtres voisines partagent k-1 valeurs, donc recalculer chaque maximum revient à répéter presque tout le travail. Mais un maximum ne peut pas être annulé : lorsque la plus grande valeur sort de la fenêtre, il faut trouver la suivante sans relire la fenêtre. Une deque monotone ne conserve que les valeurs qui pourraient encore devenir un maximum, la réponse se trouvant à son début.
Parcourir chaque fenêtre
Correcte, mais ne termine pas sur les plus gros tests
Intuition
Lisez les valeurs k de chaque fenêtre et conservez la plus grande. Chaque fenêtre est lue en entier, son maximum ne peut donc pas être manqué. Chacune des n-k+1 fenêtres nécessite k lectures, le pire cas étant lorsque k est environ égal à la moitié de n : n = 2 × 10^4 et k = 10^4 donnent environ 10^4 fenêtres de 10^4 valeurs, soit 10^8 lectures.
Algorithme
- Parcours
startde 0 àn-k. - Prends la plus grande valeur parmi
nums[start]ànums[start+k-1]. - Ajoute-la au résultat, puis renvoie le résultat après la boucle.
def maxSlidingWindow(nums, k):
result = []
for start in range(len(nums) - k + 1):
# Read all k values of this window again
result.append(max(nums[i] for i in range(start, start + k)))
return resultBlocs avec les maxima de chaque côté
Intuition
Découpez le tableau en blocs de k éléments : indices 0 à k-1, puis k à 2k-1, et ainsi de suite, avec un dernier bloc plus court si k ne divise pas n. Une fenêtre a exactement k éléments : elle correspond donc à un bloc entier, ou à la fin d’un bloc suivie du début du suivant.
Pré-calculons donc fromStart[i], la plus grande valeur depuis le début du bloc de i jusqu’à i, et toEnd[i], la plus grande valeur de i jusqu’à la fin de son bloc. La fenêtre commençant à i se termine à i+k-1 : toEnd[i] couvre sa partie gauche et fromStart[i+k-1] sa partie droite ; la plus grande des deux est donc son maximum. Dans le premier exemple, la fenêtre [2, 12, 3] utilise toEnd[1] = 12 et fromStart[3] = 3, ce qui donne 12.
Trois parcours donnent un temps en O(n), au prix de deux tableaux auxiliaires de longueur n et de la nécessité de disposer du tableau entier avant de produire la première réponse.
Algorithme
- Remplissez
fromStartde gauche à droite, en recommençant avecnums[i]lorsqueiest un multiple dek. - Remplissez
toEndde droite à gauche, en recommençant avecnums[i]au dernier indice et partout oùi+1est un multiple dek. - Pour chaque début
ide 0 àn-k, ajoutez le plus grand detoEnd[i]etfromStart[i+k-1].
def maxSlidingWindow(nums, k):
n = len(nums)
# Cut nums into blocks of k: indices 0..k-1, k..2k-1, and so on.
from_start = [0] * n # max from the start of i's block up to i
to_end = [0] * n # max from i up to the end of i's block
for i in range(n):
if i % k == 0:
from_start[i] = nums[i]
else:
from_start[i] = max(from_start[i - 1], nums[i])
for i in range(n - 1, -1, -1):
if i == n - 1 or (i + 1) % k == 0:
to_end[i] = nums[i]
else:
to_end[i] = max(to_end[i + 1], nums[i])
# A window [i, i+k-1] is the tail of one block plus the head of the next.
return [max(to_end[i], from_start[i + k - 1]) for i in range(n - k + 1)]Deque monotone d’indices
Intuition
Si l’indice j précède i et que nums[j] ≤ nums[i], alors j ne peut plus jamais être un maximum : toute fenêtre ultérieure qui contient j contient aussi i, qui sort plus tard. Ainsi, lorsque i arrive, tu peux oublier j.
Garde une deque des indices pas encore oubliés. Lorsque i arrive, retire les indices à l’arrière tant que leurs valeurs sont inférieures ou égales à nums[i], puis ajoute i. Les valeurs restantes diminuent strictement de l’avant vers l’arrière, donc l’indice à l’avant correspond au maximum de la fenêtre. Stocke les indices, car l’indice à l’avant doit aussi sortir lorsque la fenêtre le dépasse. Dans le premier exemple, à l’indice 5, la deque contient 12, 8 et 5 ; 12 se trouve à l’indice 5 - 3 = 2, donc il sort et la réponse est 8.
Chaque indice est ajouté une fois et retiré au plus une fois : au plus 2n opérations sur la deque, en temps O(n). La deque ne contient jamais plus de k indices.
Algorithme
- Pour chaque indice
i, retirez les indices à l’arrière tant que la deque n’est pas vide et que la valeur à son arrière est inférieure ou égale ànums[i]. - Ajoutez
ià l’arrière. - Si l’indice à l’avant est égal à
i-k, il a quitté la fenêtre : retirez-le. - Dès que
i ≥ k-1, ajoutez au résultat la valeur correspondant à l’indice à l’avant.
from collections import deque
def maxSlidingWindow(nums, k):
window = deque() # indices; their values strictly decrease from front to back
result = []
for i, x in enumerate(nums):
# A value at the back that is not bigger than x can never be a maximum again.
while window and nums[window[-1]] <= x:
window.pop()
window.append(i)
# The front index has slid out of the window on the left.
if window[0] == i - k:
window.popleft()
# From index k-1 on, every step completes a window; its maximum sits at the front.
if i >= k - 1:
result.append(nums[window[0]])
return result
Pièges et cas limites
- Stocker des valeurs plutôt que des indices. Avec
[3, 1, 3]etk = 2, le deuxième 3 dépile le premier, puis est lui-même supprimé parce qu'il est égal ànums[0], la valeur qui a quitté la fenêtre. - Répondre trop tôt ou trop tard. La première fenêtre complète se termine à l'indice
k-1, et le résultat doit contenir exactementn-k+1valeurs. - Supprimer
i-k+1au lieu dei-k. Cet indice correspond encore à la première valeur de la fenêtre. - Lire l'arrière de la deque sans vérifier qu'elle contient quelque chose.
- Dans l'approche par blocs, oublier que le dernier bloc peut être plus court que
k. Le parcours de droite à gauche doit recommencer au dernier indice ainsi qu'à la fin de chaque bloc.
Questions fréquentes3
Quelle est la complexité temporelle du maximum de fenêtre glissante ?
La solution utilisant une deque monotone s’exécute en O(n) temps, car chaque indice est ajouté une fois et retiré au plus une fois. La deque contient au plus k indices, donc l’espace supplémentaire est de O(k), en plus du résultat.
Peut-on résoudre le problème du maximum dans une fenêtre glissante avec un tas ?
Oui. Empile des paires valeur et indice dans un tas max, et avant de lire le sommet, retire-le tant que son indice est en dehors de la fenêtre. Cela s’exécute en O(n log n) et peut contenir jusqu’à n entrées. La file à double extrémité est plus rapide et moins volumineuse, car elle élimine les valeurs inutiles dès qu’une plus grande arrive.
Quelle est la différence entre une deque monotone et une pile monotone ?
L’extrémité arrière du deque fonctionne comme une pile monotone : avant d’empiler une valeur, tu dépiles celles qu’elle rend inutiles. Le deque ajoute une sortie par l’avant pour les valeurs trop anciennes. Le prochain élément supérieur n’a pas de date d’expiration, il ne nécessite donc que la pile. Inverse la comparaison et le deque donne le minimum de chaque fenêtre.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
def maxSlidingWindow(nums, k):
# Écrivez le code iciTest #1
Test #2
Test #3
Arguments
nums = [4, 2, 12, 3, 8, 5, 1] k = 3
Résultat attendu
[12, 12, 12, 8, 8]