Monotonic Deque Sliding Window Maximum

Problem

Return the maximum of every contiguous window of size k.

Use a monotonic deque of indices whose values are decreasing: before appending a new index pop smaller values from the back, and pop the front when it has fallen outside the window.

Return the list of window maxima. Return [] when k is not positive or larger than the array.

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: [[9,8,7],5]

expected: []

case 4

in: [[4,4,4],2]

expected: [4,4]

case 5

in: [[1,-1],1]

expected: [1,-1]

Starter codePython

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

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