You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Input: nums = [1], k = 1
Output: [1]
 

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

We may observe that in a window, the elements that come before the largest element will never be selected as the largest element of any future windows. For example, consider a window [1, 2, 3, 4, 1]. Because the window is sliding left to right, any window with the first three elements 1, 2, and 3 would also have the 4.

However, we cannot ignore the items that follow the largest element. If we use the above example, we cannot ignore the last element 1 since there may be a window from the fourth index (0-based indexing) until the eighth index where 1 is the largest element. The elements at indices 3 and 4 are those that will be "useful" in the following windows.

Therefore, we can discard the first three elements and only take into account the elements at indices 3 and 4.

Now, let's consider the next element and call it x. We need to add x to the window to consider the next window. If x > 1, then we can now discard the 1 because x will be in any future windows that 1 is in. If x > 4, we can discard the 4 as well for the same reason.

To perform these operations, we can use a monotonic queue as it supports efficient insertion, deletion, and retrieval of elements from the ends of a window. We will implement it with the deque data structure.

A monotonic data structure is one where the elements are always sorted. In our case, we want a monotonic decreasing queue, which means that the elements in the queue are always sorted descending. When we want to add a new element x, we maintain the monotonic property by removing all elements less than x before adding x.

We initialize a deque of integers dq. It will contain the indices of the "useful" elements in the current window. The reason we need to store the indices instead of the elements themselves is that we need to detect when elements leave the window due to sliding too far to the right.

We also initialize an array of integers res to store the answer.

• Create a deque dq of integers.
• Create a list of integers res to store the answer.
• Iterate over the first k elements from i = 0 to k - 1 and perform the following:
• While dq is not empty and the current element nums[i] is greater or equal to nums[dq.peekLast()], continue to pop the last element.
• Push i at the end of dq.
• Push the largest element of the first window nums[dq.peekFirst()] to the answer.
• We iterate over all the remaining elements from i = k to n - 1 to move to the next windows. We perform the following in this loop:
• Check if the element at the front of dq is equal to i - k. If it is equal to i - k, it cannot be included in the current window. We pop this element.
• While dq is not empty and the current element nums[i] is greater or equal to nums[dq.back()], continue to pop the last element.
• Push i at the end of dq.
• Push the largest element of the current window nums[dq.peekFirst()] to the answer.
• Return res.

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> dq = new ArrayDeque<>();
        List<Integer> res = new ArrayList<>();

        for (int i = 0; i < k; i++) {
            while (!dq.isEmpty() && nums[i] >= nums[dq.peekLast()]) {
                dq.pollLast();
            }
            dq.offerLast(i);
        }
        res.add(nums[dq.peekFirst()]);

        for (int i = k; i < nums.length; i++) {
            if (dq.peekFirst() == i - k) {
                dq.pollFirst();
            }
            while (!dq.isEmpty() && nums[i] >= nums[dq.peekLast()]) {
                dq.pollLast();
            }

            dq.offerLast(i);
            res.add(nums[dq.peekFirst()]);
        }
        // Return the result as an array.
        return res.stream().mapToInt(i->i).toArray();
    }
}

Time Complexity - O(N)

Space Complexity - O(K)