Problem: Sliding Window Maximum

Let’s look at a classic deque problem: reporting the largest value in a window as the window slides across an array.

We have worked with this kind of window before. In the queue chapter, the Moving Average practice problem keeps the last k readings, with the newest added at one end and the oldest removed at the other, and after each reading it reports their average. This problem uses the same sliding window. The difference is what we compute for each window: the maximum instead of the average.

Let’s trace a small example: values = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3. The first window is the first three values:

[1, 3, -1], -3, 5, 3, 6, 7    maximum is 3

Then the window slides one position to the right:

1, [3, -1, -3], 5, 3, 6, 7    maximum is 3

Then again:

1, 3, [-1, -3, 5], 3, 6, 7    maximum is 5

Continuing this way, the answer is:

[3, 3, 5, 5, 6, 7]

There are six windows. One starts at each index from 0 through 5, and a window that starts at index 6 or 7 would run past the end of the array.

The signature of the method in Java might look like this:

public static int[] slidingMaximum(int[] values, int k) {
  // Your implementation goes here
}

There is one constraint: the solution must run in $O(n)$ time, where $n$ is the length of values.

Let’s think of some special or edge cases as well:

• If k is 1, every window contains one value, so the answer is a copy of the input.
• If k is values.length, there is only one window, so the answer has one value: the maximum of the whole array.

You may assume k is valid: at least 1 and at most values.length, so there is always at least one window.