Sliding Window Maximum
Du erhältst ein Array aus Ganzzahlen nums und eine Fenstergröße k. Ein Fenster aus k aufeinanderfolgenden Werten beginnt am linken Ende und bewegt sich jeweils um eine Position nach rechts, bis sein rechter Rand auf dem letzten Wert liegt. Gib an jeder Position von links nach rechts den größten Wert im Fenster zurück: n-k+1 Werte für ein Array der Länge n.
Funktion
- numsinteger-array
- das Array, über das das Fenster gleitet
- kinteger
- die Anzahl der Werte in jedem Fenster
- Gibt zurückinteger-array
- der größte Wert jedes Fensters, vom ganz linken Fenster bis zum ganz rechten
Einschränkungen
1 ≤ k ≤ nums.length ≤ 2 × 104-104 ≤ nums[i] ≤ 104- Das Ergebnis enthält
nums.length-k+1Werte, einen pro Fenster, von links nach rechts geordnet.
Beispiele
- Eingabe
- nums = [4, 2, 12, 3, 8, 5, 1]k = 3
- Ausgabe
- [12, 12, 12, 8, 8]
- Erklärung
- 12 liegt in den ersten drei Fenstern, daher lautet die Antwort bei jedem davon 12. Nachdem es herausgeschoben wurde, haben sowohl
[3, 8, 5]als auch[8, 5, 1]den größten Wert 8.
- Eingabe
- nums = [-3, -1, -7, -2]k = 2
- Ausgabe
- [-1, -1, -2]
- Erklärung
- Die Fenster sind
[-3, -1],[-1, -7]und[-7, -2]. Die größere von zwei negativen Zahlen ist diejenige, die näher bei null liegt. Das ergibt -1, -1 und -2.
- Eingabe
- nums = [6, 6, 1]k = 3
- Ausgabe
- [6]
- Erklärung
- Wenn
kder Länge des Arrays entspricht, gibt es ein Fenster: das ganze Array. Sein größter Wert ist 6; das zweite Vorkommen von 6 ergibt keine zweite Antwort.
Weiterführende Frage
Kannst du eine Warteschlange erstellen, die das Hinzufügen eines Werts am Ende, das Entfernen des Werts am Anfang und das Lesen ihres aktuellen Maximums jeweils in amortisierter Zeit von O(1) unterstützt?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Das Durchsuchen jedes Fensters nach seinem größten Wert kostet
kSchritte pro Fenster. Vergleiche zwei benachbarte Fenster: Sie habenk-1Werte gemeinsam, weil ein Wert links herausfällt und rechts ein Wert hinzukommt.Wenn ein neuer Wert hinzukommt, kann jeder ältere Wert im Fenster, der kleiner oder gleich diesem ist, nie wieder ein Maximum sein. Der neue Wert bleibt in jedem späteren Fenster, das den älteren noch enthält, und ist mindestens genauso groß. Du kannst diese älteren Werte endgültig verwerfen.
Bewahre die Indizes der Werte, die in einer doppelseitigen Warteschlange verbleiben, wobei ihre Werte von vorne nach hinten strikt abnehmen. Entferne für jeden neuen Index kleinere oder gleiche Werte vom Ende, füge den Index hinzu, entferne den vordersten Eintrag, wenn er aus dem Fenster herausgerutscht ist, und lies das Maximum des Fensters am Anfang ab.
Lösung
Benachbarte Fenster haben k-1 Werte gemeinsam, daher wiederholt die Neuberechnung jedes Maximums fast die gesamte Arbeit. Ein Maximum lässt sich jedoch nicht rückgängig machen: Wenn der größte Wert aus dem Fenster herausrutscht, brauchst du den nächstgrößten, ohne das Fenster erneut durchzugehen. Eine monotone Deque behält nur die Werte, die noch zu einem Maximum werden könnten; die Antwort steht an ihrer Spitze.
Scanne jedes Fenster
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Lies die k Werte jedes Fensters und behalte den größten. Jedes Fenster wird vollständig gelesen, sodass sein Maximum nicht übersehen werden kann. Für jedes der n-k+1 Fenster sind k Lesezugriffe nötig; im ungünstigsten Fall ist k etwa halb so groß wie n: n = 2 × 10^4 und k = 10^4 ergeben etwa 10^4 Fenster mit je 10^4 Werten, also 10^8 Lesezugriffe.
Algorithmus
- Iteriere
startvon 0 bisn-k. - Nimm das größte Element von
nums[start]bisnums[start+k-1]. - Füge es dem Ergebnis hinzu und gib das Ergebnis nach der Schleife zurück.
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 resultBlöcke mit Maxima von jeder Seite
Idee
Teile das Array in Blöcke der Länge k auf: Indizes 0 bis k-1, dann k bis 2k-1 und so weiter; der letzte Block ist kürzer, wenn k kein Teiler von n ist. Ein Fenster ist genau k Elemente lang, also entweder ein ganzer Block oder das Ende eines Blocks zusammen mit dem Anfang des nächsten.
Berechne daher im Voraus fromStart[i], den größten Wert vom Anfang des Blocks von i bis einschließlich i, und toEnd[i], den größten Wert von i bis zum Ende seines Blocks. Das bei i beginnende Fenster endet bei i+k-1: toEnd[i] deckt seinen linken Teil ab und fromStart[i+k-1] seinen rechten Teil, daher ist der größere der beiden Werte das Maximum des Fensters. Im ersten Beispiel nimmt das Fenster [2, 12, 3] die Werte toEnd[1] = 12 und fromStart[3] = 3, woraus 12 folgt.
Drei Durchläufe benötigen O(n) Zeit, allerdings zwei Hilfsarrays der Länge n und das gesamte Array, bevor die erste Antwort ausgegeben werden kann.
Algorithmus
- Fülle
fromStartvon links nach rechts und beginne mitnums[i]von vorn, wenniein Vielfaches vonkist. - Fülle
toEndvon rechts nach links und beginne mitnums[i]am letzten Index und überall dort von vorn, woi+1ein Vielfaches vonkist. - Füge für jeden Startindex
ivon 0 bisn-kden größeren Wert vontoEnd[i]undfromStart[i+k-1]hinzu.
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)]Monotone Deque von Indizes
Idee
Wenn der Index j vor i kommt und nums[j] ≤ nums[i], kann j nie wieder ein Maximum sein: Jedes spätere Fenster, das j enthält, enthält auch i, das später das Fenster verlässt. Wenn i hinzukommt, kannst du j also vergessen.
Führe eine Deque mit den Indizes, die noch nicht vergessen wurden. Wenn i hinzukommt, entferne von hinten Indizes, deren Werte höchstens nums[i] sind, und füge dann i hinzu. Die verbleibenden Werte sind von vorne nach hinten streng fallend, also ist der vorderste Wert das Maximum des Fensters. Speichere Indizes, denn der vorderste Index muss ebenfalls entfernt werden, sobald das Fenster über ihn hinausrückt. Im ersten Beispiel enthält die Deque bei Index 5 die Werte 12, 8 und 5; 12 steht an Index 5 - 3 = 2, also wird es entfernt und die Antwort ist 8.
Jeder Index wird einmal hinzugefügt und höchstens einmal entfernt: höchstens 2n Deque-Operationen, O(n) Laufzeit. Die Deque enthält nie mehr als k Indizes.
Algorithmus
- Für jeden Index
ientferne Indizes vom Ende, solange die Deque nicht leer ist und der Wert an ihrem Ende höchstensnums[i]beträgt. - Füge
iam Ende ein. - Wenn der vorderste Index gleich
i-kist, hat er das Fenster verlassen: Entferne ihn. - Sobald
i ≥ k-1gilt, füge den Wert am vordersten Index zum Ergebnis hinzu.
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
Stolperfallen und Grenzfälle
- Werte statt Indizes speichern. Bei
[3, 1, 3]undk = 2entfernt die zweite 3 die erste aus der Warteschlange und wird dann selbst entfernt, weil sie gleichnums[0]ist, dem Wert, der das Fenster verlassen hat. - Zu früh oder zu spät antworten. Das erste vollständige Fenster endet am Index
k-1, und das Ergebnis muss genaun-k+1Werte enthalten. i-k+1statti-kentfernen. Dieser Index ist noch der erste Wert des Fensters.- Das letzte Element der Deque lesen, ohne zu prüfen, ob sie etwas enthält.
- Beim Blockansatz vergessen, dass der letzte Block kürzer als
ksein kann. Der Durchlauf von rechts nach links muss sowohl am letzten Index als auch an jedem Blockende neu beginnen.
Häufige Fragen3
Wie hoch ist die Zeitkomplexität des Sliding Window Maximum?
Die Lösung mit einer monotonen Deque läuft in O(n)-Zeit, da jeder Index einmal eingefügt und höchstens einmal entfernt wird. Die Deque enthält höchstens k Indizes, daher beträgt der zusätzliche Speicherbedarf zusätzlich zum Ergebnis O(k).
Kann das Maximum eines gleitenden Fensters mit einem Heap ermittelt werden?
Ja. Füge Wert- und Indexpaarungen in einen Max-Heap ein, und entferne vor dem Auslesen des obersten Elements so lange das oberste Element, wie sein Index außerhalb des Fensters liegt. Das läuft in O(n log n) Zeit und kann bis zu n Einträge enthalten. Die Deque ist schneller und benötigt weniger Speicher, weil sie nutzlose Werte entfernt, sobald ein größerer Wert eintrifft.
Was ist der Unterschied zwischen einer monotonen Deque und einem monotonen Stack?
Das Ende der Deque funktioniert wie ein monotoner Stack: Bevor du einen Wert hinzufügst, entfernst du die Werte, die dadurch nutzlos werden. Die Deque hat zusätzlich am Anfang einen Ausgang für Werte, die zu alt sind. Beim nächsten größeren Element gibt es kein Ablaufdatum, daher wird nur der Stack benötigt. Drehst du den Vergleich um, liefert die Deque das Minimum jedes Fensters.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def maxSlidingWindow(nums, k):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argumente
nums = [4, 2, 12, 3, 8, 5, 1] k = 3
Erwartete Ausgabe
[12, 12, 12, 8, 8]