题目：滑动窗口
描述
给定一个长度为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 = " ")
