Sliding Window Maximum
Module 9 · Queues
Problem
Given nums and window size k, return the maximum of each
contiguous window of size k as it slides left to right.
Examples
Example 1
Input
nums = [1,3,-1,-3,5,3,6,7], k = 3Output[3,3,5,5,6,7]Example 2
Input
nums = [1], k = 1Output[1]Windows for the first case: [1,3,-1] [3,-1,-3] [-1,-3,5] [-3,5,3]
[5,3,6] [3,6,7].
Constraints
1 ≤ n ≤ 10⁵ · 1 ≤ k ≤ n · a hard problem — the O(n) solution is a famous interview finale.
Attempt it first
Stage 1's final problem. The deque lesson built the exact machine this needs and proved its two rules; your work is assembling it into windowed form and getting the off-by-ones right. If you internalized the dominance argument, you can write this without looking back — try.