Monotonic Queue
A deque kept sorted so the window maximum is always at the front.
Sliding Window Maximum: Maximum of every 3
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.