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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @param size int整型 
# @return int整型一维数组
#
from collections import deque
class Solution:
    
    # def maxInWindows(self , num: List[int], size: int) -> List[int]:
    # """ method 1: 根据自己的理解完成"""
    #     # write code here
    #     rst = list() 
    #     n = len(num) - size
    #     if size < 1:
    #         return rst
    #     for i in range(n + 1):
    #         print("====> num[{0}]: {1}, window: {2}, max: {3}".format(i, num[i], num[i:i+size], max(num[i:i+size])))
    #         rst.append(max(num[i:i+size]))
    #     return rst

    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        """
        method2: 参考， 使用双向队列解题。
        思路： 
        step1: 双向队列来存储数列下标
        step2: 检查窗口大小与数组大小
        step3: 遍历第一个窗口，如果即将进入队列的下标的值大于队列后方的值，一次将小于的值拿出来去掉，再加入，保证队列是递增序列。
        step4: 遍历后续窗口， 每次取出队首就是最大值， 如果某个下标已经过了窗口，则从队列前方将其弹出；
        step5. 对于以后的窗口，重复step3，至数组结束。。
        """
        res = []
         #窗口大于数组长度的时候，返回空
        if size <= len(num) and size != 0:
            from collections import deque
            #双向队列
            dq = deque()
            #先遍历一个窗口
            for i in range(size):
                #去掉比自己先进队列的小于自己的值
                while len(dq) != 0 and num[dq[-1]] < num[i]:
                     dq.pop()
                dq.append(i)
            #遍历后续数组元素
            for i in range(size, len(num)):
                res.append(num[dq[0]])
                while len(dq) != 0 and dq[0] < (i - size + 1):
                    #弹出窗口移走后的值
                    dq.popleft()
                #加入新的值前，去掉比自己先进队列的小于自己的值 
                while len(dq) != 0 and num[dq[-1]] < num[i]:
                    dq.pop()
                dq.append(i)
            res.append(num[dq[0]])
        return res
		
		
		第二中方法没看明白