【Python数据结构与算法】队列----滑动窗口

题目：滑动窗口

描述
给定一个长度为n（n<=100,000）的整数序列。有一个大小为k(0 < k <= n)的滑动窗口从数组的最左端移动到最右端。你可以看到窗口中的k个数。窗口每次向右滑动一个数的距离。
下面是一个例子：
数组是 [1 3 -1 -3 5 3 6 7]， k = 3。

窗口位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7

你的任务是得到滑动窗口在每个位置时的最大值和最小值。

输入
输入包括两行。
第一行包括n和k，分别表示数组的长度和窗口的大小。
第二行包括n个数。
输出
输出包括两行。
第一行包括窗口从左至右移动的每个位置的最小值。
第二行包括窗口从左至右移动的每个位置的最大值
样例输入

8 3
1 3 -1 -3 5 3 6 7

样例输出

-1 -3 -3 -3 3 3
3 3 5 5 6 7

AC代码

import collections
n,k = map(int,input().split())
a = list(map(int,input().split()))
dqMax = collections.deque()
dqMin = collections.deque()
minA,maxA = [],[]  
for i in range(n): 
    while len(dqMax) > 0 and a[dqMax[-1]] < a[i]: 
        dqMax.pop()
    dqMax.append(i)  
    while len(dqMin) > 0 and a[dqMin[-1]] > a[i]:
        dqMin.pop()  
    dqMin.append(i)
    if len(dqMax) > 0 and dqMax[0] <= i-k: 
        dqMax.popleft()
    if len(dqMin) > 0 and dqMin[0] <= i-k:
        dqMin.popleft()
    if i >= k-1: 
        maxA.append(a[dqMax[0]])  
        minA.append(a[dqMin[0]])
for e in minA:
    print(e,end = " ")
print()
for e in maxA:
    print(e,end = " ")