Sliding Window Maximum with Deque

Problem

Return the maximum of every contiguous window of size k as a list, in left-to-right order.

Use a deque of indices holding candidates in decreasing value order: pop smaller values from the back when adding a new index, and pop the front once it falls out of the window. Return an empty list when k is non-positive or larger than the list.

Hint

The deque front is always the index of the current window maximum.

Test cases

case 1

in: [[1,3,-1,-3,5,3,6,7],3]

expected: [3,3,5,5,6,7]

case 2

in: [[1],1]

expected: [1]

case 3

in: [[],3]

expected: []

case 4

in: [[9,8,7,6],2]

expected: [9,8,7]

case 5

in: [[4,2,12,3,8],3]

expected: [12,12,12]

Starter codePython

def max_sliding_window(nums, k):
    # Your code here
    pass

5 test cases · run your code against them in the editor