Python simple solution (176 ms) + explanation


  • 1
    T
    class Solution(object):
        def maxSlidingWindow(self, nums, k):
            if k<2:
                return nums
                
            # Find max of first window
            mx = max(nums[:k])
            m = [mx]
            for i in xrange(len(nums)-k):
                # If number before window is max, compute new max
                if nums[i]==mx:
                    mx=max(nums[i+1:i+k])
                # If rightmost number > max, set max to 
                if nums[i+k]>mx:
                    mx=nums[i+k]
                m.append(mx)
            return m
    

    First the max value of the first window is found

    max(nums[:k])
    

    At each step in the loop, we want the max of the window: xi [xi+1 .. xi+k-1 xi+k] xi+k+1

    First we look at xi. If it is equal to the maximum if the last window [xi .. xi+k-1], we compute the maximum of the window xi [xi+1 .. xi+k-1], and save as the max

    Then we look at the rightmost value of the window xi+k. If it is larger than the max, the max is now xi+k

    Lastly the max is added to m, the array of max'es.


    The worst case is O(kn).

    If the input array is strictly ascending, the runtime would be k+n, as the max of the sliding window is always increasing.

    The worst case input is an array which is sorted descending, as the maximum value would be recomputed at every step, but it seems there are not many of those tests cases, as the algorithm beats 99.13% of the Python answers.


    Examples:

    Best case:

    nums = [1, 2, 3, 4, 5], k = 3
    mx = max([1,2,3]) (=3)
    m = [3]
    loop:
      1, [2, 3, 4], 5
        i=0, nums[i]=1 (not mx), nums[i+k]=4,  mx=4,  m=[3,4]
      1, 2, [3, 4, 5]
        i=1, nums[i]=2 (not mx), nums[i+k]=5,  mx=5,  m=[3,4,5]
    

    Worst case:

    nums = [5, 4, 3, 2, 1], k = 3
    mx = max([5,4,3]) (=5)
    m = [5]
    loop:
      5, [4, 3, 2], 1
        i=0, nums[i]=5 (=mx), mx=max([4,3]), nums[i+k]=2,  m=[5,4]
      5, 4, [3, 2, 1]
        i=1, nums[i]=4 (=mx), mx=max([3,2]), nums[i+k]=1,  m=[5,4,3]
    

    In the last example, max(window) is computed at every step, hence O(kn)


Log in to reply
 

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