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