Important thing to note is that, MaxQueue on its own has a O(N) time in enqueue.

However, in the context of this question, the overall running time is O(N) because the queue will only operate once on each item.

```
from collections import deque
class MaxQueue:
def __init__(self):
self.max_q = deque()
self.q = deque()
def enqueue(self, item):
while self.max_q and self.max_q[-1] < item:
self.max_q.pop()
self.q.append(item)
self.max_q.append(item)
def dequeue(self):
popped = self.q.popleft()
if popped == self.max_q[0]:
self.max_q.popleft()
return popped
def get_max(self):
if self.max_q: return self.max_q[0]
else: return None
class Solution:
# @param {integer[]} nums
# @param {integer} k
# @return {integer[]}
def maxSlidingWindow(self, nums, k):
if not nums: return []
q = MaxQueue()
for num in nums[:k]:
q.enqueue(num)
results = []
cur_max = q.get_max()
results.append(cur_max)
for i in xrange(k, len(nums)):
cur_num = nums[i]
q.dequeue()
q.enqueue(cur_num)
results.append(q.get_max())
return results
```