Sliding Window Maximum - Implementation

Here is the implementation using a monotonic deque:

function maxSlidingWindow(nums, k):
    deque = empty deque (stores indices)
    result = []

    for i from 0 to nums.length - 1:
        // Remove indices outside window
        while deque not empty and deque.front() <= i - k:
            deque.popFront()

        // Remove smaller elements
        while deque not empty and nums[deque.back()] < nums[i]:
            deque.popBack()

        deque.pushBack(i)

        if i >= k - 1:
            result.append(nums[deque.front()])

    return result

$O(n)$ time (each index added/removed once), $O(k)$ space for deque.