Monotonic Queue

What it is

A monotonic queue is a queue kept in order so the best candidate in the current window is easy to access.

It usually stores indices, not only values.

When to use it

It appears often when the problem asks for:

• window maximum
• window minimum
• sliding-window queries for the best element

Common mistake

The classic mistake is thinking “if there is a queue, I can just enqueue everything.”

If you do not remove elements that became irrelevant, the queue loses its advantage.

Better question

Before using it, ask:

1. does the window move one step at a time?
2. do I need the best element of the window all the time?
3. have some older elements become strictly worse than the newer ones?