Solution: A Deque of Indices

Let’s build the solution step by step.

public static int[] slidingMaximum(int[] values, int k) {
  int[] answer = new int[values.length - k + 1];
  // ...
  return answer;
}

We maintain a deque of candidate indices.

Deque<Integer> candidates = new ArrayDeque<>();

We loop over the indices of the array values.

for (int i = 0; i < values.length; i++) {
  // ...
}

For each index i, we do three things.

First, remove expired indices from the front of the deque candidates. At position i, the current window begins at i - k + 1, so any index <= i - k is outside the window:

while (!candidates.isEmpty()
    && candidates.getFirst() <= i - k) {
  candidates.removeFirst();
}

Second, evict indices from the back. If the new value is greater than or equal to the value at the last candidate, that last candidate can never be the maximum of any later window:

while (!candidates.isEmpty()
    && values[candidates.getLast()] <= values[i]) {
  candidates.removeLast();
}

Third, add the new index at the back:

candidates.addLast(i);

Once the first full window exists, the index of the maximum for the current window is at the front:

if (i >= k - 1) {
  answer[i - k + 1] = values[candidates.getFirst()];
}

Here it is in full:

public static int[] slidingMaximum(int[] values, int k) {
  int[] answer = new int[values.length - k + 1];
  Deque<Integer> candidates = new ArrayDeque<>();

  for (int i = 0; i < values.length; i++) {
    // Remove candidates that are no longer in the window.
    while (!candidates.isEmpty() && candidates.getFirst() <= i - k) {
      candidates.removeFirst();
    }

    // Remove candidates that the new value makes useless.
    while (!candidates.isEmpty()
        && values[candidates.getLast()] <= values[i]) {
      candidates.removeLast();
    }

    candidates.addLast(i);

    // The front is the maximum once the first full window exists.
    if (i >= k - 1) {
      answer[i - k + 1] = values[candidates.getFirst()];
    }
  }

  return answer;
}

Notice values[candidates.getLast()] <= values[i] uses <= rather than <. This means that when a new value is equal to the value at the last candidate, the last candidate is removed and replaced by the new index. Using < instead would also be correct: the index of the older equal value would stay in the deque until it expired, and while it was at the front it would report the same maximum. We prefer <= because it keeps the deque smaller: it never holds two candidates of equal value. And the one it keeps is the newer of the two, which has a larger index and so stays inside the window longer.

When we stated the problem, we listed some edge cases. Let’s check the solution against them.

• If k is 1, each new index removes the previous one from the back if the previous value is less than or equal to the new value, or the previous one expires on the next step. Either way, each window has one item, and the method records each value as its own maximum.
• If k is values.length, the method processes the whole array before recording the first and only answer. The candidate at the front is the maximum of the whole array.