代码随想录 -- 栈与队列 -- 滑动窗口最大值

239. 滑动窗口最大值 - 力扣（LeetCode）

思路：

采用自定义单调队列

单调队列主要的三个函数：push()  pop()  getMax()

1. push(val)

如果队列非空：当 val 比队尾元素大时，删除队尾元素，直到队尾元素比 val 大，将 val 加入队尾

2. pop(val)

如果要删除的元素在队首，删除队首元素；否则不需要删除

3. getMax()

返回队首元素

主函数实现

1. 将前 k 个元素先加入队列中，并找出第一次滑动窗口的最大值加入 res 数组

2. 从 nums 第二个元素开始遍历，删除第 i-1 个元素，加入第 i+k-1 个元素，将本次滑动窗口最大值加入 res 数组

class MyQueue(object):def __init__(self):self.queue=deque()def push(self,val):# while len(self.queue)!=0 and self.queue[0]<val:#     del self.queue[0]while len(self.queue)!=0 and self.queue[-1]<val:del self.queue[-1]self.queue.append(val)def pop(self,val):if val==self.queue[0]:del self.queue[0]def getMax(self):return self.queue[0]class Solution(object):def maxSlidingWindow(self, nums, k):de1=MyQueue()res=[]for i in range(0,k):de1.push(nums[i])res.append(de1.getMax())for i in range(1,len(nums)-k+1):de1.pop(nums[i-1])de1.push(nums[i+k-1])res.append(de1.getMax())return res