具体方法参考labuladong的特殊数据结构：单调队列，python重写
239. 滑动窗口最大值
import collections # 创建一个单调队列的类, 队头大--->队尾小 class MonotonicQueue(object): def __init__(self): # 创建一个双向list self.queue = deque() def getmax(self): # 得到单调队列里面的最大值(队头) if len(self.queue) > 0: return self.queue[0] def popout(self, n): # 由于n很可能已经被后面来的更大的元素给排出了队列中, 所以先要判断一下是否存在先 if self.queue[0] == n: # 如果在的话, 该元素就是队头 return self.queue.popleft() def pushin(self, n): # 和单调栈很像, 如果当前元素比队尾元素大, 则队尾元素出队 while(len(self.queue) > 0 and self.queue[-1] < n): self.queue.pop() # 从队尾入队接受审判 self.queue.append(n) class Solution(object): def maxSlidingWindow(self, nums, k): """ :type nums: List[int] :type k: int :rtype: List[int] """ res = list() windows = MonotonicQueue() # 下面的代码虽然符合逻辑但是最后得到的结果会少一个 # for i in range(len(nums)): # if (i < k): # q.pushin(nums[i]) # else: # res.append(q.getmax()) # 这里get的max其实是i-1的 # q.popout(nums[(i - 1) - k + 1]) # 这里退出的元素也是i-1的 # q.pushin(nums[i]) for i in range(len(nums)): # 在windows里面有k个之前，一直加进 if (i < k-1): windows.pushin(nums[i]) else: # 加入第k个, windows.pushin(nums[i]) # 得到window里面的最大值 res.append(windows.getmax()) # 得到window中的最大值之后再删除窗口中的最后一个元素 windows.popout(nums[i - k + 1]) return res
