Given an array of integers and a value k, find the length of the longest subarray with max-gap no more than k

I'm struggling with this problem: you are given an array $A$ of $n$ integers and a number $k \in \mathbb{N} : k \neq 0$. The problem asks to find an algorithm that runs in $\Theta(n)$ that returns the length of the longest subarray $A'$ in $A$ s. t. $\max(A')-\min(A') \leq k$.

For example, in the array $A = \{6, 5, 9, 10, 7, 13, 8, 7, 5, 15\}$ with $k = 6$ the algorithm must return 6, because the subarray $A' = \{9, 10, 7, 13, 8, 7\}$ has length 6 and the difference between its maximum and its minimum is no more than 6.

Another example, with $A = \{1, 3, 5, 2, 3, 1, 7\}$ with $k = 2$ the result is 3, because the subarray $A' = \{2, 3, 1\}$ has length 3 and the difference between its maximum and minimum is less or equal than 2.

So far I tried to build an algorithm that goes like this (it may be buggy, it's just a draft to make my idea of solution clear):

int test(int* arr, int len, int k) {
    int minIndex = 0;
    int maxIndex = 0;
    int start = 0;
    int end = 0;
    int maxLength = 0;
    for (int i = 1; i  arr[maxIndex])
            maxIndex = i;
        // Check the new maximum/minimum doesn't make the subarray invalid
        if (arr[maxIndex] - arr[minIndex] > k) {
            // We broke the subarray, check the length of the longest subarray until now
            if (end - start > maxLength)
                maxLength = end - start;

            // Restart from the second element, then the third, and so on
            start++;
            maxIndex = minIndex = start;
            i = start;
        }
    }

    return maxLength;
}

The main problem with this algorithm is that in the worst case it runs in $\Theta(n^2)$, which doesn't comply with the problem's requests.

Basic idea:
Use 2 pointers to traverse the array: start and end. Both start at the beginning of the array. Try moving end one position at a time and track the maximum subarray length, until the gap is too large. When that happens, move start towards end until you have smaller gap or you meet with the end pointer (the subarray becomes empty).

How to evaluate the gap: by definition max - min of current subarray. So we keep track of min and max.

Have a min deque where you keep elements in ascending order, so that the head of the queue will be the current minimum.
When encountering a new element: remove all elements larger than it from the back of the queue, then add the new element to the back of the queue. This guarantees ascending ordering.

Have a max deque where you keep elements in descending order, so that the head of the queue will be the current maximum.
When encountering a new element: remove all elements smaller than it from the back of the queue, then add the new element to back of the the queue. This guarantees descending ordering.

NB: You don't keep the elements themselves in the min and max queues; instead, keep their indices in the original array! This way you have both position and value, which is important for the following step.

When the gap becomes too large: obviously you cannot increase end before first bringing start closer to it. So increate start by one. Now check the head of both queues: they are the indices of current min and current max. If any (or both) these indices are now lower than start, then they don't belong to the current subarray anymore. Drop them, the head of the queue will be the new min/max.

Continue until end reaches the end of the array.

This gives you linear complexity: each element is processed once, and added and removed at most once from each queue.

Java implementation:

public int find(int[] numbers, int maxGap) {
    int best = 0;
    int bestStart = 0, bestEnd = 0;

    Deque minQueue = new LinkedList<>();
    Deque maxQueue = new LinkedList<>();

    int start = 0, end = 0;

    while (end = x) {
            minQueue.removeLast();
        }
        minQueue.addLast(end);

        // add end to the maxQueue keeping decreasing order
        while (!maxQueue.isEmpty() && numbers[maxQueue.peekLast()]  maxGap) {
            start++;
            if (start > minQueue.peekFirst()) {
                minQueue.removeFirst();
            }
            if (start > maxQueue.peekFirst()) {
                maxQueue.removeFirst();
            }
        } else {

            // track progress
            if (end - start + 1 > best) {
                best = end - start + 1;
                bestStart = start;
                bestEnd = end;
            }

            end++;
        }
    }

    // debug
    for (int i = bestStart; i <= bestEnd; i++) {
        System.out.print(numbers[i] + " ");
    }
    System.out.println();

    return best;
}

StackExchange Computer Science Q#93057, answer score: 4