摘要
Title: 154. 滑动窗口
Tag: 单调队列
Memory Limit: 64 MB
Time Limit: 1000 ms

154. 滑动窗口

题意
思路

注意！！！单调队列维护的是下标，不是元素（下图中的append(5)，5是下标）

单调栈和单调队列核心思想？
先把朴素算法想清楚，再看朴素算法里面，栈和队列中哪些元素是没有用的，然后把这些元素删掉，看是否有单调性，若有就可以优化

单调队列板子题，复杂度 $O(n)$

单调队列：给定一个序列，求出长度不超过k的滑动窗口中（最小/最大）的值

代码

数组模拟队列

模拟一个以x为对头，长度小于等于k的窗口

'''
Author: NEFU AB-IN
Date: 2022-02-27 11:29:42
FilePath: \ACM\Acwing\154.py
LastEditTime: 2022-02-27 14:55:44
'''
N = int(1e6 + 10)

q = [0] * N

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

    hh, tt = 0, -1
    for i in range(n):
        #维持滑动窗口的大小
        #当队列不为空(hh <= tt) 且 当当前滑动窗口的大小(i - q[hh] + 1)>我们设定的
        #滑动窗口的大小(k),队列弹出队列头元素以维持滑动窗口的大小
        while hh <= tt and i - q[hh] + 1 > k:
            hh += 1
        #构造单调递增队列
        #当队列不为空(hh <= tt) 且 当队列队尾元素>=当前元素(a[i])时,那么队尾元素
        #就一定不是当前窗口最小值,删去队尾元素,加入当前元素(q[ ++ tt] = i)
        while hh <= tt and nums[q[tt]] >= nums[i]:
            tt -= 1
        tt += 1
        q[tt] = i
        if i >= k - 1:
            print(nums[q[hh]], end=" ")
    print()
    hh, tt = 0, -1
    for i in range(n):
        if hh <= tt and i - k + 1 > q[hh]:
            hh += 1
        if hh <= tt and nums[q[tt]] <= nums[i]:
            tt -= 1
        tt += 1
        q[tt] = i
        if i >= k - 1:
            print(nums[q[hh]], end=" ")

deque

'''
Author: NEFU AB-IN
Date: 2022-02-27 14:47:16
FilePath: \ACM\Acwing\154.1.py
LastEditTime: 2022-02-27 14:54:31
'''
from collections import deque

N = int(1e6 + 10)
q = deque()

if __name__ == "__main__":
    n, k = map(int, input().split())
    nums = list(map(int, input().split()))
    for i in range(n):
        while q and i - q[0] + 1 > k:
            q.popleft()
        while q and nums[q[-1]] >= nums[i]:
            q.pop()
        q.append(i)
        if i >= k - 1:
            print(nums[q[0]], end=" ")

    q.clear()
    print()

    for i in range(n):
        while q and i - q[0] + 1 > k:
            q.popleft()
        while q and nums[q[-1]] <= nums[i]:
            q.pop()
        q.append(i)
        if i >= k - 1:
            print(nums[q[0]], end=" ")

154. 滑动窗口

题意

思路

代码