monotonicqueue

A monotonic queue is a data structure that maintains its elements in either non-decreasing or non-increasing order. When new elements are added, the queue is modified to preserve this monotonic property. Typically, this involves removing elements from the back of the queue that violate the desired order before adding the new element. For example, in a non-decreasing monotonic queue, if a new element is smaller than the last element in the queue, the last element is removed. This process continues until the new element can be added while maintaining the non-decreasing order.

Monotonic queues are often implemented using a double-ended queue (deque), which allows efficient insertion and deletion from both ends. The primary advantage of a monotonic queue is its ability to efficiently find the minimum or maximum element within a sliding window. As the window slides, elements are added to the back and removed from the front. The monotonic property ensures that the first element of the queue is always the minimum (for a non-decreasing queue) or maximum (for a non-increasing queue) element within the current window. This makes them useful in algorithms that require finding extrema in a dynamic range, such as the sliding window maximum/minimum problem.