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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @param size int整型 
# @return int整型一维数组
# 滑动窗口
class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        # write code here
        from collections import deque
        if size == 0:
            return [] # 特殊情况
        res = [] # 存放结果
        DQ = deque([]) # 队列存放窗口内的（索引， 数字）这个元组对，索引的作用是可以判断上次的最大值这一次还在不在窗口里
        for i, i_num in enumerate(num): # 遍历
            if not DQ: # 队列为空直接塞入
                DQ.append((i, i_num))
            else: # 队列不空，按照降序排列（保证队首的是该窗口内的最大元素），把小于当前值的元组对pop出去
                if i_num < DQ[-1][1]: # 比队尾还小正常入队
                    DQ.append((i, i_num))
                else: # 弹出队尾小数，压入当前数
                    while DQ and DQ[-1][1] < i_num:
                        DQ.pop()
                    DQ.append((i, i_num))

            if i >= size-1: # 达到窗口数量
                if i - DQ[0][0] >= size: # 判断上一次的最大值这次在不在窗口，不在就弹掉
                    DQ.popleft()
                res.append(DQ[0][1]) # 存起来队首元素记为当前的窗口最大
        return res