Algorytmy i struktury danych · Senior · Pytanie 55 z 75
Co daje monotoniczny deque w zadaniu „maksimum w przesuwanym oknie”?
- 1Medianę każdego okna w O(1)
- ✓Poprawna odpowiedź: Maksimum każdego okna w O(1), O(n) łącznie
- 3Posortowaną kopię każdego okna w O(log n)
Wyjaśnienie
Deque trzyma indeksy malejących wartości: nowe wartości zdejmują mniejsze z końca, a indeksy, które wyszły z okna, są usuwane z początku. Każdy indeks wchodzi i wychodzi raz. Mediana wymaga dwóch kopców.