题解 | #滑动窗口的最大值#

用双向队列deque实现一个单调队列

# -*- coding:utf-8 -*-
from collections import deque
class MonotonicQueue():
    def __init__(self):
        self.q = deque()
    def push(self, n):
        while self.q and self.q[-1] < n:
            self.q.pop()        
        self.q.append(n)
    def popleft(self, n):
        if self.q[0] == n:
            self.q.popleft()            
    def peek(self):
        if self.q:
            return self.q[0]
        else:
            return None 

class Solution:
    def maxInWindows(self, num, size):
        # write code here
        nums = num
        k = size
        if k == 0 or k > len(nums):
            return []

        mq = MonotonicQueue()
        for i in range(k):
            mq.push(nums[i])
        res = [mq.peek()]
        for i in range(k, len(nums)):
            mq.popleft(nums[i-k])            
            mq.push(nums[i])            
            res.append(mq.peek())            
        return res