AlgoScope

Monotonic Queue

A deque kept sorted so the window maximum is always at the front.

Data structures, data structure, intermediate
The maximum of window 0 to 2 is 3, the front of the deque.active 0-21031-12-3354356677fronti
The maximum of window 0 to 2 is 3, the front of the deque.active 0-21031-12-3354356677fronti

Sliding Window Maximum: Maximum of every 3

Step, step 6 of 23

Window 0 to 2 is complete. Its maximum is the front of the deque, 3, read in O(1).

Cost

Push with pops
O(1) amortized
Pop front
O(1)
Space
O(k)

Before this

Leads to

Topics that need this one first.

Taught by the same lesson

Sliding Window Maximum covers these too, in the same run.