Python o(n) time 180ms


  • 0
    W
    class Solution(object):
        def maxSlidingWindow(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: List[int]
            """
            if not nums:
                return []
            
            local_m = nums[0]
            local_p = 0
            res =[]
            for i in range(1,k): #find the max value of the first k numbers
    
                if nums[i] >= local_m:
                    local_m, local_p = nums[i], i
            res.append(local_m)
    
          
            for i in range(k, len(nums)):
                start_p = i - k+1
                if local_p >= start_p:   # if the previously saved max position is in the window, and current #number smaller than the maxvalue, store the number
                    if local_m > nums[i]:
                        res.append(local_m)
                    elif local_m <= nums[i]:
                        local_p = i
                        local_m = nums[i]
                        res.append(local_m)
                else:  #Otherwise, search the new max_val and max position in the current windows. 
                    local_m = nums[i]
                    local_p = i
                    for j in range(start_p, i):
                        if nums[j] >= local_m:
                            local_m, local_p = nums[j], j
                    res.append(local_m)
                        
            return res

  • 1
    Y

    I think the worstcase is O(kn), right?


Log in to reply
 

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