题解 | #滑动窗口的最大值#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @param size int整型 
# @return int整型一维数组
#
class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        # write code here
        len_nun = len(num)
        if len_nun < size or size == 0:
            return None
        # 核心点有两个：
        # 1. 当前值大于之前的值，之前的不可能是最大值，可以删掉-->递增序列
        # 2. 双端队列实现：要如果即将进入队列的下标的值大于队列后方的值，依次将小于的值拿出来去掉，再加入，保证队列是递增序
        # 我们加入一个双端队列存储数组下标，以及初始化结果队列
        queue = []
        res = []
        for i in range(len(num)):
            # 首先我们检查最大值是否滑出窗口
            if len(queue)>0 and i > queue[0]+size -1:
                # 滑出就弹出队首
                queue.pop(0)
            # 之后我们检查新加入元素是否更大，如果是则弹出前面所有更小的值，保证递增，这里用while实现,从后向前弹出
            while len(queue)>0 and num[queue[-1]]<num[i]:
                queue.pop()
            # 保证递增后，添加新元素入队
            queue.append(i)
            # 到第一个窗的时候，我们添加队首到res结果中
            if i+1 >=size and len(queue):
                res.append(num[queue[0]])
        return res