Acwing 154.滑动窗口

• 假设滑动的过程中新来一个数，此时这个数比队尾的数要小就弹出队尾的数，这是个while的过程，直到队尾的数比这个数要小。这样就永远保证滑动串口中最小的数在队头

N = 1000010
a = [0] * N # 存的是整个数组
q = [0] * N # 存的是下标
hh, tt = 0, -1


if __name__ == "__main__":
    n, k = map(int, input().split(' '))
    a = list(map(int, input().rstrip().split(' ')))

    for i in range(n):
        # 先判断队头是不是已经滑出窗口了或者为空队列
        if hh <= tt and i - k + 1 > q[hh]:
            hh += 1
        # 如果当前进入窗口的数比队尾的数要小，说明队尾的数永远不会被输出
        # pop队尾元素，直到队列为空或者遇到比当前数还要小的数
        while a[i] <= a[q[tt]] and hh <= tt:
            tt -= 1
        # 把当前的数加入到队尾中
        tt += 1
        q[tt] = i
        # 开始输出的时候是i-k+1>=0的时候
        if i -k + 1 >= 0:
            print(a[q[hh]], end=' ')
    print()

    hh, tt = 0, -1
    for i in range(n):
        # 先判断队头是不是已经滑出窗口了或者为空队列
        if hh <= tt and i - k + 1 > q[hh]:
            hh += 1
        # 如果当前进入窗口的数比队尾的数要大，说明队尾的数永远不会被输出
        # pop队尾元素，直到队列为空或者遇到比当前数还要大的数
        while a[i] >= a[q[tt]] and hh <= tt:
            tt -= 1
        # 把当前的数加入到队尾中
        tt += 1
        q[tt] = i
        # 开始输出的时候是i-k+1>=0的时候
        if i -k + 1 >= 0:
            print(a[q[hh]], end=' ')
    # print()

每次输入的时候都rstrip一下吧，太坑了