Algorithmusgymnastik 2

Find Maximum in Sliding Window

Erläuterung

Bei einem Array mit ganzen Zahlen und einem Fenster der Größe w wird der aktuelle Maximalwert im Fenster ermittelt, wenn das Fenster (Teil des Arrays) durch das Array gleitet.

Beispiel

Lassen Sie uns bei einer Fenstergröße von 3 alle Maxima finden, während wir schieben.

step1 Der Maximalwert unter den drei Elementen von Window ist 2

step2 Um eins verschoben, beträgt der Maximalwert unter den drei Elementen von Window 3

step3 Um eins verschoben, beträgt der Maximalwert unter den drei Elementen von Window 6

Schließlich sollte die Datenstruktur mit 2, 3 und 6 zurückgegeben werden.

Solution

Time Complexity: O(n) Alle Elemente werden nur einmal in einem einzigen Scan aus der Deque verschoben und entfernt. Push und Pop sind also O (1) Der Algorithmus arbeitet mit der Zeitkomplexität O (n).

Space Complexity: O(w) Die Raumkomplexität ist O (w), da eine Liste von Fenstergrößen verwendet wird.

Grober Algorithmusfluss

Dieser Algorithmus verwendet die Deque-Datenstruktur, um den Maximalwert im Fenster zu ermitteln. Der Zweck der Verwendung dieser Datenstruktur besteht darin, Push- und Pop-Vorgänge wie das Hinzufügen und Löschen von Daten an beiden Enden durchzuführen. Dies liegt daran, dass beide Endwarteschlangen mit O (1) arbeiten. Dies fungiert als Fenster. Hier sind zwei Punkte zu beachten.

1. Fügen Sie den Index des Elements und nicht das Element des Arrays in die Deque ein.
2. Setzen Sie den maximalen Index am Anfang der Deque und die anderen Indizes am Ende.

Zu Beginn des Algorithmus ist deque Mist, also addieren Sie den Index des Elements durch die Größe des ersten Fensters.

Wenn das hinzugefügte Element kleiner als das Element nach der Deque ist, ist das hinzugefügte Element das letzte Element der neuen Deque. Wenn das hinzuzufügende Element größer ist, platzieren Sie das Element wiederholt hinter der Deque, bis ein größeres Element gefunden wird. Schieben Sie das neue Element, das Sie als Ende hinzufügen möchten.

Wie Sie sehen können, speichert deque die Elemente in absteigender Reihenfolge. Der Anfang der Deque enthält den Index des Maximalwerts für dieses bestimmte Fenster.

Wiederholen Sie die folgenden Schritte jedes Mal, wenn sich das Fenster nach rechts bewegt.

1. Wenn das Element hinter der Deque kleiner oder gleich dem aktuell hinzuzufügenden Element ist, entfernen Sie das Element aus der Deque, bis der Index des Elements größer als das hinzuzufügende Element angezeigt wird.
2. Wenn Sie ein Fenster verschieben und der Wert nicht in das aktuelle Fenster passt, wird der erste Elementindex gelöscht.
3. Schieben Sie den Index des aktuellen Elements hinter das Fenster.

Code