sliding window, keep the big value in the double sided queue to avoid rescan
from collections import deque
class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
dq=deque()
max_numbers=[]
for i in xrange(len(nums)):
#delete all the values in the dequeue smaller than the new value
#therefore, the values in the dequeue is always in descending order
while dq and nums[i]>nums[dq[-1]]:
dq.pop()
#append the index of the new value
dq.append(i)
#if the dequeue include elements outside the window, delete it
if i>=k and dq[0]<=i-k:
dq.popleft()
#when we have scanned at least k elements
#append the left most value in the dequeue
if i>=k-1:
max_numbers.append(nums[dq[0]])
return max_numbers
