239. Sliding Window Maximum

"""
239. Sliding Window Maximum
1. 用deque来维持当前窗口的最大值，最大值放在deque的最前面q[0]以此类推。
2. 从头开始遍历数组，需要两个操作来维护deque:
    2.1 第一个操作是要把超出范围的最大的的index从deque中移除。
    2.2 第二个操作是从deque的尾部移除，比当前遍历的的值小的值的index，这样插入的值就是在它“应该”在的位置。
3. 当遍历到k以及k之后时，每次遍历就要往res里面append结果
"""
class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        res = []

        if not nums or k <= 0:
            return res

        q = collections.deque()     # 维持一个deque,当前窗口最大值在最前面。

        for i in range(0, len(nums)):
            while q and q[0] < i - k + 1:   #移除超出范围的最大值
                q.popleft()

            while q and nums[q[len(q) - 1]] < nums[i]:  # 由于越大的值与会排在deque的前面，所以从deque的尾部移除比当前值小的值的index
                q.pop()

            q.append(i)     # 经过上一步的移除，比当前值小的index都被移除了，插入当前值的index。

            if i >= k - 1:   # 当index大于等于k - 1说明我们要往res里面写值了。
                res.append(nums[q[0]])

        return res