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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @param size int整型 
# @return int整型一维数组
#
class Solution:
    def maxInWindows(self , nums: List[int], size: int) -> List[int]:
        # 用一个存储最大值的队列记录滑动窗口最大元素的idx（用idx是为了窗口越界操作）
        # 加入新元素如果比当前que中最大元素大，清que，加入新元素
        # 加入新元素如果比当前que中最大元素小，清que中比当前新元素小的元素，加入新元素
        if len(nums) == 0:
            return 0
        
        if size == 1:
            return nums
        
        que = []
        result = []
        for i in range(len(nums)):
            
            if i == 0:
                que.append(i)
                continue

            
            while i - que[0] >= size:
                que.pop(0)
                
            if nums[i] < nums[que[0]]:
                while que and nums[que[-1]] < nums[i]:
                    que.pop()
                que.append(i)
            else:
                while que:
                    que.pop(0)
                que.append(i)
            if i >= size - 1:
                result.append(nums[que[0]])
                
        return result