# Python O(N) solution using MaxQueue

• 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``````

• That's not how big-O complexity works.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.