Interview Question with Arrays and Consecutive Subintervals
Despite common belief, maintaining the maximum (or minimum) element out of the last $k$ elements does not involve a $O(\log k)$ factor, and can be done in amortized $O(1)$. Using this twice (once for max and once for min) you can solve your problem in $O(n)$.

The trick is done using a monotonic double-ended queue, one where all the elements are either in descending or ascending order. Furthermore, for each element we keep track of the index we encountered it, so we can invalidate it from the queue.

Suppose that we iterate over elements in a stream, and wish to maintain the minimum value (the maximum is analogous). Let's call the current value $x$ and the current index $i$. We first initialize an empty double-ended queue $Q$ and start iterating:


Remove all elements from the queue that would be made irrelevant by $x$. Since we know our queue is in ascending order, this is very simple, we keep
removing elements from the back that are bigger than $x$. They are now irrelevant for the window, as $x$ is newer and smaller.

while not empty(Q) and peek_back(Q).value &gt; x:
    pop_back(Q)

Add $x$ to the back of the queue, but keep track of its index as well.

push_back(Q, value=x, index=i)

Invalidate old items in the queue. We only have to do this if the item is in the front of the queue, otherwise its harmless (this lazy removal is what allows us to keep $O(1)$ time).

while peek_front(Q).index &lt;= i - window_size:
    pop_front(Q)

Now peek_front(Q) contains the smallest element in our window, so we can use it and then keep iterating.


Note that steps #2 and #4 are $O(1)$ time, and steps #1 and #3 are $O(r)$ time where $r$ is the number of removed elements from the queue. However since each element is only added once to the queue, the $O(r)$ steps must be amortized $O(1)$.