Algorithmen und Datenstrukturen · Senior · Frage 55 von 75
Was bringt eine monotone Deque bei der Aufgabe „Maximum im Schiebefenster“?
- 1Den Median jedes Fensters in O(1)
- 2Das Maximum jedes Fensters in O(1), insgesamt O(n)
- 3Eine sortierte Kopie jedes Fensters in O(log n)
Antwort zeigen
Richtige Antwort: Das Maximum jedes Fensters in O(1), insgesamt O(n)
Erklärung
Die Deque hält Indizes fallender Werte: neue Werte entfernen hinten kleinere, und Indizes, die das Fenster verlassen haben, fallen vorne weg. Jeder Index kommt einmal hinein und einmal heraus. Für einen Median braucht man stattdessen zwei Heaps.