Python o(n) time 180ms

  • 0
    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
            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]:
                    elif local_m <= nums[i]:
                        local_p = i
                        local_m = nums[i]
                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
            return res

  • 1

    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.