Queue Deque Simulation
Proficient Level

Implement the slidingWindowMaximumDeque method that returns maximum values for every sliding window of size k.

The input contains an integer array nums, its length size, and a window size k.

Your task is to move a window of size k from left to right and return the maximum value from each window.

For example, for [1,3,-1,-3,5,3,6,7] with k = 3, the window maximum values are [3,3,5,5,6,7].

Example 1
Input:
nums (int[]) = [1,3,-1,-3,5,3,6,7]
size (int) = 8
k (int) = 3
Return:
(int[]) [3,3,5,5,6,7]
Example 2
Input:
nums (int[]) = [1]
size (int) = 1
k (int) = 1
Return:
(int[]) [1]
Example 3
Input:
nums (int[]) = [9,11]
size (int) = 2
k (int) = 2
Return:
(int[]) [11]

Use a deque to store indexes of useful elements.

The deque is kept in decreasing order of values, so the front always points to the maximum value of the current window. Before adding a new index, remove smaller values from the back because they can never become the maximum while the current value is inside the window.

Also remove indexes from the front when they move outside the current window.

Pseudocode:

function slidingWindowMaximumDeque(nums, size, k):
    deque = empty deque
    result = empty array
    for i from 0 to size - 1:
        while deque is not empty and front(deque) <= i - k:
            remove front from deque
        while deque is not empty and nums[back(deque)] <= nums[i]:
            remove back from deque
        add i to back of deque
        if i >= k - 1:
            append nums[front(deque)] to result
    return result
Run your code to see the result.