Kolejka monotoniczna to deque trzymany w porządku malejącym (lub rosnącym). Dla maksimum w oknie usuwasz z końca mniejsze elementy przy dodawaniu nowego, więc na początku zawsze jest max. Usuwasz też z początku elementy, które wyszły z okna. Każdy element wchodzi i wychodzi maks. raz, więc całość to O(n).