Sliding Window

Kurz: Beim Sliding-Window-Muster schiebt man ein „Fenster” über eine Folge und aktualisiert dessen Wert nur an den Rändern, statt ihn jedes Mal neu zu berechnen.

Genauer: Statt für jede Position alle k Elemente neu zu addieren, zieht man das herausfallende Element ab und addiert das neu hinzukommende. Aus O(n·k) wird O(n).

Im Detail

• Festes Fenster: Zum Beispiel die größte Summe von k aufeinanderfolgenden Zahlen.
• Variables Fenster: Rechter Rand wächst, linker Rand rückt nach, sobald eine Bedingung verletzt ist (zum Beispiel „längster Teilstring ohne Wiederholung”).
• Hilfsstrukturen: Eine Hash-Tabelle zählt Zeichen im Fenster, ein Deque liefert Maximum im Fenster.
• Erkennen: Fragen nach „zusammenhängendem Teilstück” mit Summe, Länge oder Anzahl sind typische Kandidaten.
• Verwandt: Die Zwei-Zeiger-Technik.

Siehe auch: Zwei-Zeiger-Technik und gleitendes Fenster