The idea is to have a pointer (I call `max_idx`

) for the maximum number so far in the current window. For the first k-1 numbers, you simply assign `max_idx`

to the cell with the maximum number. For the remaining numbers, you first check if `max_idx`

is out of your window size, then you search for the current maximum number. The best case for this search is O(1) and the worst case is O(k).

```
def maxSlidingWindow(self, nums, k):
if not nums:
return []
res = []
max_idx = 0
for i, n in enumerate(nums):
if i < k-1:
if nums[max_idx] < n:
max_idx = i
else:
if max_idx < i-k+1:
max_idx = i-k+1
for j in xrange(max_idx, i, 1):
if nums[j] > nums[max_idx]:
max_idx = j
if nums[max_idx] < n:
max_idx = i
res.append(nums[max_idx])
return res
```