Given an array of integers and a window size , return the maximum value in each sliding window as it moves from left to right through the array. Example: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3. The windows are [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], [3,6,7]. The answer is [3, 3, 5, 5, 6, 7].
This is THE foundational problem for monotonic queues. Every other problem builds on this pattern. Before reading on, try to think: how would you maintain the maximum efficiently?