239. Sliding Window Maximum
利用deque，在deque里维护一个不递增序列就可以了
class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if not nums:
return []
if len(nums) <= k:
return [max(nums)]
deque = collections.deque()
# init
for i in range(k):
while deque and nums[i] > deque[-1]:
deque.pop()
deque.append(nums[i])
res = [deque[0]]
for i in range(k, len(nums)):
# add one
while deque and nums[i] > deque[-1]:
deque.pop()
deque.append(nums[i])
# remove one
if nums[i-k] == deque[0]:
deque.popleft()
res.append(deque[0])
return res
