from collections import deque

def diff_sliding_window(arr, win):
 
    if win > len(arr):
        return []
        
    win_maxes = [] # max of each window
    
    #Q contains indexes of items in the window that are greater than
	#all items to the right of them.  This always includes the last item
	#in the window
    Q = deque()

    #fill Q for initial window
    for i in range(win):
        #remove anything that isn't greater than the new item
        while len(Q) > 0 and arr[i] >= arr[Q[-1]]:
            Q.pop()
        Q.append(i)
    win_maxes.append(arr[Q[0]])
    
    for i in range(win, len(arr)):
        #remove indexes (at most 1, really) left of window
        while len(Q) > 0 and Q[0] <= (i-win):
            Q.popleft()
            
        #remove anything that isn't greater than the new item
        while len(Q) > 0 and arr[i] >= arr[Q[-1]]:
            Q.pop()
        Q.append(i)
        win_maxes.append(arr[Q[0]])
    
    return win_maxes

print(diff_sliding_window([12, 1, 78, 90, 57, 89, 56],3))
print(diff_sliding_window([1, 3, -1, -3, 5, 3, 6, 7],3))