Monotonic queue is a data structure that maintains elements in a monotonic order to optimize certain types of problems, particularly those involving ranges or sliding window maximum/minimum.
All the basic operations of a queue can be applied to a monotonic queue, but with additional constraints to maintain the monotonic property. The common operations include:
- Push: When pushing a new element onto the queue, elements that violate the monotonic property are removed from the back. For an increasing monotonic queue, elements greater than the new element are removed; for a decreasing monotonic queue, elements smaller than the new element are removed.
- Pop, front, isEmpty: These operations function the same way as in a regular queue.
The elements stored in a monotonic queue must be comparable.
Monotonic queue is particularly useful for solving problems that involve finding the maximum or minimum value in a sliding window over an array or sequence. The queue can be constructed by sweeping through the array from left to right. Along the way, some information can be collected from the queue status like the front element or auxillary variables, to solve the problem.