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

题目：https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788
法一：枚举每个窗口然后取最大值。运行超时。

class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:        
        res=[]
        for i in range(len(num)-size+1):
            winmax=max(num[i:i+size])
            res.append(winmax)
        return res

法二：维护单调（递减）队列来记录滑动窗口最大值。所以需要双端队列这个数据结构。
题解区designeer总结得很好，搬运记录一下。
图片说明

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @param size int整型 
# @return int整型一维数组
#
class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:

        res=[]
        #双端队列
        queue=[]#左边做队首，右边做队尾。做成递减队列

        for i in range(len(num)):
            if len(queue)>0 and i>queue[0]+size-1:#i走到超出原来最大值能覆盖的窗口的位置，那么这个最大值要更新了
                queue.pop(0)

            while len(queue)>0 and num[i]>num[queue[-1]]:#要进队的数数值大，那就删除所有前面小的数，再把它加进去。
                #终止时要加进去的数要么排在第一了，要么就排在比它大的数的后面
                #要加len(queue)>0 这个条件，否则当queue被删空了代码就会出现num[-1]这样索引报错的情况
                queue.pop()
            queue.append(i)

            if i>=size-1:
                res.append(num[queue[0]])               
        return res