Sliding Window Maximum
Move a fixed-size window across a sequence and see which candidate remains its earliest maximum.
Free theory articleMove a fixed-size window across a sequence and see which candidate remains its earliest maximum.
Concept & interpretation
The sliding window maximum problem asks us to find the maximum element in each contiguous subsegment of size k within a sequence of length n. A naive approach takes O(n * k) time by scanning each window, but we can optimize this to O(n) using a monotone deque (double-ended queue). The deque maintains a sequence of useful indices, dropping elements that are out of bounds or strictly smaller than the newly considered element.
Experimenting with the Module
You can interact with the monotone deque behavior by using the Sliding Window Maximum module.
- Enter
2,-1,4,4,0in Sequence and select 3 in Window k. - Use the Step button to advance element by element, observing how the deque evicts smaller values and expires old indices.
- Notice how multiple equal maximums are resolved by keeping earlier indices at the front of the deque.