Sliding Window Maximum

We can use a double-ended queue to implement a heap in this problem. We are going to do three things to this deque. If the size of our queue is bigger than the sliding window, we need to pop the first element out. Everytime we add a new number, all elements smaller than it in the queue should be popped out since they are older and won't be in our answer. Besides, we need to fetch numbers from our queue to add into our answer.

Code in Python:

from collections import deque
class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        if nums:
            que = deque([])
            ans = []
            for i in range(0, len(nums)):
                val = nums[i]
                while que and nums[que[-1]]<val:
                    que.pop()

                if que and que[0] <= i-k:
                    que.popleft()

                que.append(i)
                if i>=k-1:
                    ans.append(nums[que[0]])
            return ans
        else:
            return []