239. 滑动窗口最大值

这个题属于滑动窗口，维护一个定长的窗口，但是需要用到一个重要的知识就是单调队列。单调队列是怎么实现的呢？遍历到一个元素，和队尾的元素进行比较，如果队尾的元素比当前元素要小，就移除去。直到当前的队尾元素比当前元素要大，然后把当前元素追加到队尾。那么这个队列的队头一定是当前窗口最大的元素。

通俗点说，就是当前这个数索引更大，在窗口更靠后，和前面的元素相比，可以存在更久的时间，那么那些索引更小，值也更小的元素就没有价值了。所以要移除去。如果存在索引小，但是又比当前元素大的。虽然它存在的时间更短，但是它更强大，所以依然有价值，就要保留下来。

具体的代码实现如下，需要注意的是，移除队尾元素需要使用while。移除所有比当前元素值小的元素，而不是仅仅移除最后一个。移除之后直接把当前元素追加到队尾即可。随后检查现在队头的元素有没有在窗口之外，在窗口之外就不合法了，要移除。移除之后窗口内的元素都是合法的，然后更新答案，队头就是当前窗口最大的元素。

还有一个细节就是要注意队列里面，我们存的应该是数组的索引，而不是具体的值，如果存具体的值，后续就不知道这个数字的索引是否合法了，而存索引，我们依然能根据索引找到对应的值。

from collections import deque
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq=deque()
        res=[]
        for i,num in enumerate(nums):
            while dq and num>=nums[dq[-1]]:
                dq.pop()
            dq.append(i)
            while dq[0]<=i-k:
                dq.popleft()
            if i>=k-1:
                res.append(nums[dq[0]])
        return res