Python solution in 164 - 208ms


  • 0
    D
    class Solution(object):
        def maxSlidingWindow(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: List[int]
            """
            if len(nums) <= 1:
                return nums
            
            ma = max(nums[:k])
            p = nums.index(ma) 
            ret = [ma,]
            
            for i in range(k, len(nums)):
                ne = nums[i]
                if ne >= ma:
                    ma = ne
                    p = k -1
                elif p == 0:
                    t = nums[i-k+1:i+1]
                    ma = max(t)
                    p = t.index(ma)
                else:
                    p -= 1
                ret.append(ma)
            return ret
    

    1,for the first k nums, get the max: 'ma'; and the position of 'ma': 'p' (the 'p' show the max times that the 'ma' can be the max number)

    2,for the next next num (nums[k],nums[k+1],......):

    -case 1, new number >= 'ma',refresh ‘ma’ & 'p'

    -case 2, new number < 'ma' , & 'p' > 0, that means the 'ma' still the max number in the new window.

    -case 3, new number < 'ma' , & 'p' == 0,that means the max number already been removed, then get a new max number, also refresh 'p'

    i changed case 2 and case 3 for easier reading


  • 0
    X

    However, the worst case is like [N,N-1,N-2,N-3......,3,2,1], which means in every iteration, you will need to revaluate the max function in k-window, yielding O(Nk) complexity.


Log in to reply
 

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