单调下降队列

队头是最大值，若待加入的数大于队尾，则队尾永无作最大值的一天
删除队尾直至队尾大于待加入的数，从而队列保持单调下降

python用双向队列deque

from collections import deque
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        res = []
        q = deque() # 双向队列，存储原数组索引
        i = 0
        while i < len(nums):
            # 若队列有元素且滑动窗口最左端大于队头元素的索引，则当前队头元素不在窗口中，删除
            if len(q) > 0 and i - k + 1 > q[0]: q.popleft()
            # 若待加入的数大于队尾,则删除队尾
            while len(q) > 0 and nums[q[-1]] <= nums[i]:
                q.pop()
            # 此时队列元素均大于待加入元素，将待加入元素索引插到队尾，
            q.append(i)
            # 当前索引 + 1大于等于滑动窗口长度，则可以输出队头元素作为答案
            if i >= k - 1: 
                res.append(nums[q[0]])
            i += 1 # 滑动窗口右移动一格
        return res