Data Structure: Sliding Window Minimum / Monotonic Queue

Given an array of elements \( a_0, a_1, a_2, \ldots, a_n \), and queries Q(i,i+L) which means "find the minimum element in \(a_i, a_{i+1}, \ldots, a_{i+L}\) ". How can we answer such queries efficiently?

We can have an \(O(n \lg{n})\) complexity by using a minimum priority queue, RB tree, or a binary tree representation of multiset, but there in this setting we can implement a data structure called monotonic queue which only requires \(O(n)\) in construction. The implementation of this data structure requires a dequeue.

Let D be the dequeue which maintain a pair of information (i, \(a_i\)). An important property of D that we will maintain is that element in D will always be in sorted order (invariant). We will first start with an empty D, and will insert \(a_i\) and remove elements from D accordingly as we iterate from the left to the right of array \(a\) (which is from i = 0, 1, 2, ..., n).

Suppose that we are now at index \(i\) and considering to add \(a_i\). Notice that when \(a_i\) is added, all elements in (j, \(a_j\)) in D such that \(a_j\) is bigger than \(a_i\) can never be a minimum value as we go forward, hence they can be removed from D. Furthermore, if the element (i-L-1, \(a_{i-L-1}\)) is in D (which will be located at the top of D if it exists), we remove that element as well. Lastly, we append \(a_i\) at the back of D. Then we will have Q(i-L, i) = the top element in D when we reach index i. Since each element will enter and leave D only once, we have a total of \(O(N)\) operations. :D