Sliding Window Maximum (Monotonic Deque)

core

Implement window_max(a, k) returning the maximum of every contiguous window of length k in a, in order: the result has a.size() - k + 1 entries, where entry j equals the max of a[j .. j + k - 1]. Assume 1 <= k <= a.size(). The intended tool is a deque of candidate indices, values decreasing from front to back: before pushing index i, pop any back indices whose value is <= a[i] (they can never win again); before reading the window max, pop any front index that has fallen out of the current window (front <= i - k).

Example: window_max({1,3,-1,-3,5,3,6,7}, 3) returns {3,3,5,5,6,7}: the max of [1,3,-1] is 3, of [3,-1,-3] is 3, of [-1,-3,5] is 5, of [-3,5,3] is 5, of [5,3,6] is 6, of [3,6,7] is 7.

Tests include a case with n up to 8*10^5, so your solution must run in O(n) total, not O(n*k).

Input format: each test in tests/*.in is laid out as:

Line 1: the mode letter L.
Line 2: n k, the array length and the window size.
Line 3: the n values, space-separated.

A performance test is instead the single line G 800000 400000 321 (mode G): the harness builds the length-n array itself from the seed and compares a checksum of window_max's result, so your function still receives an ordinary array and window size.

Test 05.in reads:

L
1 1
42

This is a one-element array with window size 1; the only window is {42}.

Where you'll use it:

✦ Solution & editorial unlock with the pass.