The largest number in every window

Given a list of numbers and a size k, report the largest number in each window of k consecutive numbers.

Worked example#

For [1, 3, -1, -3, 5, 3, 6, 7] with k = 3:

So the answer is [3, 3, 5, 5, 6, 7].

Why the usual window trick fails#

A running sum slides beautifully: one number joins, one leaves, add and subtract. A running maximum does not, and it is worth being precise about why.

Adding is reversible: subtracting undoes it. Taking a maximum is not. If the number leaving the window happened to be the maximum, the new maximum is somewhere in the remaining k - 1 numbers and nothing you kept can tell you where. You would have to look again.

So this is not a harder sliding window. It is a window whose state cannot be undone, and it needs a different structure.

The idea#

Keep a deque of positions, holding only the numbers that could still be the maximum of some future window, largest at the front.

When a new number arrives, any number already waiting that is smaller or equal is finished. It cannot be the maximum of any window from here on, because the new number is at least as large and will stay in the window longer. So pop those off the back.

Then push the new position on the back, and drop the front if it has fallen out of the window on the left. The front is now the answer.

The two ends, and why both are needed#

• The back is where the monotonic-stack logic happens: overtaken numbers leave.
• The front is where the window logic happens: numbers that aged out leave.

A stack could do the first and a queue could do the second. This needs both, which is exactly what a deque is for, and this problem is the clearest reason that structure exists.

Constraints#

• 1 <= k <= n <= 100000
• -1000000000 <= nums[i] <= 1000000000