leetcode-239. 滑动窗口最大值

239. 滑动窗口最大值

本题维护一个长度为 k 的滑动窗口，并在每次移动后查询最大值。可以用单调队列保存候选元素：新元素到来时，从队尾移除值小于或等于它的元素，再把新元素加入队尾。对应的值从队头到队尾严格递减，移除过期位置后，队头就是当前窗口的最大值。

这样删除不会漏掉答案：新元素的位置更靠后，离开窗口也更晚。如果前面的元素值还不大于它，就不会再成为后续窗口的最大值，可以移除。反过来，前面的元素虽然更早过期，但只要值更大，在过期之前仍可能是答案，需要保留。

实现时，移除队尾元素要用 while，将所有不大于当前值的候选都移除，而不是只删最后一个。加入新元素后，再检查队头是否已经离开窗口，移除过期位置。窗口长度达到 k 时，将队头对应的值加入答案。

队列里保存的是数组索引，而非元素值。索引既能用来检查是否过期，也能通过原数组取出对应的值。

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