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
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
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.
nums = [1, 2, 3, 4, 5], k = 3 mx = max([1,2,3]) (=3) m =  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]
nums = [5, 4, 3, 2, 1], k = 3 mx = max([5,4,3]) (=5) m =  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