239. 滑动窗口最大值

题目链接：https://leetcode.cn/problems/sliding-window-maximum/
难度：困难

描述：
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。

提示：
1 <= k <= nums.length <= 100000

题解

from collections import deque
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = deque()
        for i in range(k):
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i)
        ret = [0] * (len(nums) - k + 1)
        ret[0] = nums[q[0]]
        for i in range(k, len(nums)):
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i)
            if q[0] <= i - k:
                q.popleft()
            ret[i-k+1] = nums[q[0]]
        return ret