Sliding Window Maximum

这道题一般都是用最优解来做，即双端队列deque，我们保存的始终是一个单调下降的队列，且保存的是元素的下标而不是元素本身，当队头元素的下标超过了当前sliding window的范围后就被弹出，如果当前元素比队尾元素大则一直弹出直到队尾元素大于当前元素为止

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        result = []
        deque = collections.deque()
        n = len(nums)

        for i in xrange(n):
            while deque and nums[deque[-1]] <= nums[i]:
                deque.pop()
            deque.append(i)
            if deque[0] < i - k + 1:
                deque.popleft()
            if i >= k - 1:
                result.append(nums[deque[0]])

        return result

双端队列的做法是O(n)的算法，这里还有普通的用最大堆的做法

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        result = []
        heap = []

        for index, num in enumerate(nums):
            heapq.heappush(heap, [-num, index])
            while heap[0][1] < index - k + 1:
                heapq.heappop(heap)
            if index >= k - 1:
                result.append(-heap[0][0])
        return result