Here's the approach in pseudo-code:
function maxSlidingWindow(nums, k)
deque := empty deque of indices
result := []
for i from 0 to n-1
// Remove indices outside window
while deque not empty and deque.front() < i - k + 1
deque.popFront()
// Remove smaller elements from back
while deque not empty and nums[deque.back()] <= nums[i]
deque.popBack()
deque.pushBack(i)
if i >= k - 1 then
result.append(nums[deque.front()])
return result
Time: because each index is pushed and popped at most once. Space: for the deque.
Time complexity: .
Space complexity: .