```
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)`