[JAVA] Gymnastique algorithmique 2

Find Maximum in Sliding Window

La description

Étant donné un tableau d'entiers et une fenêtre de taille w, trouve la valeur maximale actuelle dans la fenêtre lorsque la fenêtre (partie du tableau) glisse à travers le tableau.

Exemple

Avec une taille de fenêtre de 3, trouvons tous les maximums en glissant.

Screen Shot 2019-11-30 at 4.43.41.png

step1 La valeur maximale parmi les trois éléments de Window est 2 Screen Shot 2019-11-30 at 4.45.17.png

step2 Décaler de un, la valeur maximale parmi les trois éléments de Window est 3 Screen Shot 2019-11-30 at 4.48.23.png

step3 Décaler de un, la valeur maximale parmi les trois éléments de Window est 6 Screen Shot 2019-11-30 at 4.49.18.png

Enfin, la structure de données contenant 2, 3 et 6 doit être renvoyée.

Solution

Time Complexity: O(n) Tous les éléments sont poussés et sortis de deque une seule fois en une seule analyse. Push et pop sont O (1), donc L'algorithme fonctionne avec la complexité temporelle O (n).

Space Complexity: O(w) La complexité de l'espace est O (w) car elle utilise une liste de tailles de fenêtre.

Flux d'algorithme approximatif

Cet algorithme utilise la structure de données deque pour trouver la valeur maximale dans la fenêtre. Le but de l'utilisation de cette structure de données est de pousser et d'afficher des opérations telles que l'ajout et la suppression de données aux deux extrémités. C'est parce que les deux extrémités des files d'attente fonctionnent avec O (1). Cela agit comme une fenêtre. Il y a deux points à noter ici.

  1. Mettez l'index de l'élément, et non l'élément du tableau, dans le deque.
  2. Mettez l'index maximum au début de deque et les autres index à la fin.

Au début de l'algorithme, deque est de la merde, alors ajoutez l'index de l'élément par la taille de la première fenêtre.

Si l'élément que vous ajoutez est plus petit que l'élément après le deque, l'élément ajouté sera le dernier élément du nouveau deque. Si l'élément à ajouter est plus grand, faites sauter l'élément à plusieurs reprises derrière le deque jusqu'à ce qu'un élément plus grand soit trouvé. Poussez le nouvel élément que vous souhaitez ajouter comme fin.

Comme vous pouvez le voir, deque stocke les éléments dans l'ordre décroissant. Le début de la deque contient l'index de la valeur maximale pour cette fenêtre particulière.

Répétez les étapes suivantes à chaque fois que la fenêtre se déplace vers la droite.

  1. Si l'élément derrière le deque est inférieur ou égal à l'élément courant à ajouter, supprimez l'élément du deque jusqu'à ce que l'index de l'élément plus grand que l'élément à ajouter apparaisse.
  2. Si vous déplacez une fenêtre et que la valeur ne rentre pas dans la fenêtre courante, le premier index d'élément est supprimé.
  3. Poussez l'index de l'élément courant derrière la fenêtre.

Code Screen Shot 2019-11-30 at 4.17.08.png Screen Shot 2019-11-30 at 4.17.22.png

Recommended Posts

Gymnastique algorithmique 12
Gymnastique algorithmique 10
Gymnastique algorithmique 3
Gymnastique algorithmique 9
Gymnastique algorithmique 14
Gymnastique algorithmique 2
Gymnastique algorithmique 7
Gymnastique algorithmique 15
Gymnastique algorithmique 16
Gymnastique algorithmique 8
Gymnastique algorithmique 17
Gymnastique algorithmique 18
Gymnastique algorithmique 11
Exercice d'algorithme 5
Gymnastique algorithmique 4
Gymnastique algorithmique 24 sous-ensembles
Gymnastique algorithmique 23 Intervalles de fusion
Gymnastique d'algorithme 20 Supprimer les doublons
Algorithme Gymnastique 21 Cycle LinkedList
Algorithme Gymnastique 24 Tri cyclique
Gymnastique d'algorithme 19 Sous-chaîne sans répétition
Exercice d'algorithme 6
Gymnastique algorithmique 24 Inverser une liste liée
Algorithme Python
Exercices d'algorithme 13
Gymnastique d'algorithme 20 paires avec somme cible
Gymnastique algorithmique 22 Mise au carré d'un tableau trié
Gymnastique algorithmique 24 Milieu de la liste liée
Mémorandum Python (algorithme)
Algorithme d'apprentissage du dictionnaire
Algorithme de recherche de chaînes