Python Solution using dequeue


  • 0
    E

    This solution use collection.deque( ). The dequeue maintain the elements in the current window and possible maximum value.

    import collections
    class Solution:
        # @param {integer[]} nums
        # @param {integer} k
        # @return {integer[]}
        def maxSlidingWindow(self, nums, k):
            n = len(nums)
            dq = collections.deque()
            result = [0 for x in range(n-k+1)]
            for i in range(k):
                while dq and nums[i]>nums[dq[-1]]:
                    dq.pop()
                dq.append(i)
        
            for i in range(n-k):
                result[i] = nums[dq[0]] #The max value if at the front
                while dq and dq[0]<=i: #Pop out the elements that are not in window
                    dq.popleft()
                while dq and nums[dq[-1]]<nums[i+k]:
                    dq.pop()
                dq.append(i+k)
            result[-1] = nums[dq[0]] #Last iteration
            return result

Log in to reply
 

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