The Sliding Window Maximum

Given an array $nums$ and a window size $k$, return an array containing the maximum of each sliding window.

Example: $nums = [1, 3, -1, -3, 5, 3, 6, 7]$, $k = 3$ Windows: $[1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], [3,6,7]$ Maxes: $[3, 3, 5, 5, 6, 7]$ Naive approach: for each window, scan all $k$ elements to find the max.

Time: $O(nk)$. With a monotonic deque, you can do this in $O(n)$.