leetcode239 单调队列求解滑动窗口最大值**

image

利用单调队列的方式能把该题的复杂度将为O（N）具体思路为 设置一个双端队列来维护窗口内数据最多纪录窗口大小K个元素 ，由于采用单调队列所以队列中的元素是严格按照元素大小递减的方式，为了维护窗口的可是范围，即窗口以外的元素要及时丢掉 ，队列中保存的并不是元素本身而是元素在原数组当中的序号或则索引。算法可描述为：

1.先设置一个结果列表（数组） 数组长度为 length(nums)+1-k

2. 遍历整个数组，当i>=k-1的时候开始记录将队列中最左边元素（最大元素）添加到结果集合中res中

3. 维护双端队列做以下两个判断:

  a. 如果队列左部的序号超出窗口范围（n<i-k+1）时候把对头元素移除掉，保证队列中 的元素个数不能超过K个

  b. 循环处理队尾元素，当队尾元素小于当前元素则移除队尾元素直至队尾元素大于当前元素，此时当前元素入栈

  c. 此时双端队列里面维护的从左到右恰恰是第一大、第二大、。。。。。第K大的元素

程序的运行过程可以如下列表格所示：

1552192844(1).png

程序代码为：

def maxSlidingWindow(self, nums, k):

    from collections import deque

    """

    :type nums: List[int]

    :type k: int

    :rtype: List[int]

    """

    length = len(nums)

    res = []

    q= deque()

    for idx ,v in enumerate(nums):

        #检查如果左边界超出窗口就弹出队列头

        if len(q)>0 and q[0]<=idx -k:

            t =q.popleft()

        #循环检查队尾是否大于当前元素

        while  len(q)>0  and  nums[q[-1]]< v:

            q.pop()

        q.append(idx)

        if (idx>=k-1):

            res.append(nums[q[0]])

    return res