单调队列

文章目录

1. 题目链接

单调队列是一种用来解决滑动窗口最大值的数据结构。考虑数组$\{a_n\}$与窗口长度k，窗口从左向右滑动，如何在O(n+k)的时间复杂度内得到所有这些窗口内的最大值。此时就会用到单调队列，队列的插入与删除规则如下：

记插入元素的值为val，插入之前删除队列中所有小于val的元素。

记删除元素的值为val，比较队头元素的值是否相等，若相等则删除队头元素。

单调队列的Python实现

class Mqueue():
    def __init__(self, n=0):
        self.low, self.high=0, 0
        if n==0:
            self._list=[]
        else:
            self._list=[0]*n
    
    def join(self, val):
        while self.low<self.high and self._list[self.high-1]<val:
                self.high-=1
        if self.low==self.high:
            self.low, self.high=0, 0
        if self.high==len(self._list):
            self._list.append(val)
        else:
            self._list[self.high]=val
        self.high+=1
    
    def remove(self):
        retval=None
        if self.low<self.high:
            retval=self._list[self.low]
            self.low+=1
        if self.low==self.high:
            self.low, self.high=0, 0
        return retval

题目链接

滑动窗口最大值