You are given an array of integers nums and a sliding window of size w that moves from left to right across the array, shifting one position at a time.

Your task is to find the maximum value within the current window at each step and return it.

Constraints:

• $1 \leq$ nums.length $\leq 10^3$

• $-10^4 \leq$ nums[i] $\leq 10^4$

• $1 \leq$ w $\leq$ nums.length

So far, you’ve probably brainstormed some approaches on how to solve this problem. Let’s explore some of these approaches and figure out which one to follow while considering time complexity and any implementation constraints.

A naive approach is to slide the window over the input list and find the maximum in each window separately. We iterate over the input list, calculating the maximum element in each window linearly, and then adding it to the output list. In each subsequent iteration, we update the current window by removing the first element from the current window and adding the incoming element of the input list. Once we are done iterating the input list, we return the output list, containing the maximums of all $(n−w+1)$ windows.

The time complexity of this approach is $O(n \times w)$. Since we only iterate over the input list once to find all the windows, the time complexity of this part will be $O(n)$. Furthermore, removing the first element, adding the incoming element, and finding the maximum element in the window take $O(w)$ time. The space complexity of this approach is $O(w)$, since we maintain a list for the window.

We’ll use a sliding window technique combined with a deque (double-ended queue). The idea is to maintain a deque of indexes of elements in the current window such that their corresponding values are in decreasing order. The front of the deque will always store the index of the maximum element of the window.

As we iterate through nums, for each element:

• We remove smaller elements from the back of the deque since they can’t be the maximum for the current or any future window containing the current element.

• If the index at the front of the deque falls out of the current window, we remove it.

• After processing the first w elements, we start appending the value at the front of the deque to the result list, as it represents the maximum for the current window.

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Build the solution using a list

Our goal is to avoid recomputing the maximum value from scratch at every step. To do this, we maintain a list called current_window, which stores the indexes of useful elements. By useful, we mean elements that could still be the maximum in the current or any upcoming window. The list is kept in decreasing order of values in nums, i.e., ...