python solution with no extra space and time is O(n)


  • 0
    def maxSlidingWindow(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: List[int]
            """
            if nums==None or len(nums)==0:
                return []
            l,r=0,k
            while r<=len(nums):
                maxN=max(nums[l:r])
                nums[l]=maxN
                l+=1
                r=l+k
            return nums[0:l]
    

  • 0
    P

    I wouldn't say time is O(n). You're using a built in function, max, for which time is O(n).


  • 0
    T

    It seems you just took the function sum() for granted...the result could be a O(n^2)


  • 0
    R

    This is O(n*k) , because you are finding out max(in list of size k) for every iteration.


Log in to reply
 

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