LeetCode-滑动窗口最大值

"""
题目来源
https://leetcode.cn/problems/sliding-window-maximum/
"""
from collections import deque

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        # 记录所有区间长度为k的最大值
        ans = []
        # 单调递减队列, 从队首到队尾降序
        # 入队和出队的都是元素的索引
        q = deque()
        for i, v in enumerate(nums):
            # 1.入队列
            while q and v >= nums[q[-1]]:
                q.pop()
            q.append(i)
            # 2.出队列
            # 单调队列的长度限制为k, 当队列元素个数大于k就需要将队首元素出队
            if i - q[0] + 1 >= k + 1:
                q.popleft()
            # 3.开始记录答案
            if i >= k - 1:
                # 单调队列降序, 队首元素为区间最大值
                ans.append(nums[q[0]])
        return ans

# s = Solution()
# print(s.maxSlidingWindow(nums=[1, -1], k=1))