LC 239滑动窗口最大值Sliding Window Maximum　困难

返回数组中每个大小为 k 的滑动窗口内的最大值。

思路 单调递减队列存下标：队首即当前窗口最大值，队首出窗则弹出，新元素从队尾挤掉较小者。时间 O(n)。

class Solution:
    def maxSlidingWindow(
        self, nums: List[int], k: int,
    ) -> List[int]:
        q = deque()  # 存下标，对应值单调递减
        ans = []
        for i, x in enumerate(nums):
            while q and nums[q[-1]] <= x:
                q.pop()
            q.append(i)
            if q[0] == i - k:  # 队首滑出窗口
                q.popleft()
            if i >= k - 1:
                ans.append(nums[q[0]])
        return ans