Python O(N) solution using MaxQueue


  • 2
    S

    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

  • 0
    C

    That's not how big-O complexity works.


Log in to reply
 

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