面试题59：队列的最大值

题目一：
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

思路：
初始化队列，缓存数组res以及下标i，当size大于0并别i小于数组的长度时循环，如果队列不为空并且下标i+1-size>队列的第0个数，说明队列的第0个元素过期，因此需要弹出第0个元素；当队列不为空并且队列中最后一个数字对应的元素小于当前i值对应的元素时，队列循环pop出队尾的元素；然后每次将当前索引添加到队列中，当i>=size-1时，将队列第0个元素对应的数组值添加到res，返回res即可。

代码实现：

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        if not num or size > len(num) or size<1:
            return []
        queue = [] #队列
        res = []  #保存滑动窗口的最大值
        i = 0    #下标索引
        while i < len(num):
            if len(queue)>0 and i-size+1 > queue[0]:   #队列的首元素对应的元素过期，应该pop
                queue.pop(0)
            while len(queue)>0 and num[queue[-1]]< num[i]:  
            #比新进入的索引对应元素小的话则丢弃，因为加入这个索引对应的元素之后不可能为最大值
                queue.pop()
            queue.append(i)
            if i >=size-1:  #当遍历过的元素个数大于等于size，可以开始输出窗口内的最大值
                res.append(num[queue[0]])
            i+=1
        return res

提交结果：

题目二：
队列的最大值

思路：
使用list的 pop(0)复杂度是O(n)，需要用deque，初始化队列q和mxq，最大值队列mxq是一个递增队列，返回最大值时，返回队列中的最后一个元素即可；

添加元素时需要将mxq队列中的第0个元素与value相比，如果第0个元素小于value，说明此时最大的值不可能时第0个元素，只可能是value，所以从左边pop出第0个元素，知道第0个元素不小于value时，将value添加到队列的左边。

删除元素时需要判断是不是pop出了最大值，如果是的话需要将最大值也从mxq中pop出。

代码实现：

class MaxQueue:
    import collections
    def __init__(self):
        self.q = collections.deque([])
        self.mxq = collections.deque([])

    def max_value(self) -> int:
        if not self.mxq:
            return -1
        return self.mxq[-1]   #队列为递增队列，最大值在最后

    def push_back(self, value: int) -> None:
        self.q.append(value)
        while self.mxq and self.mxq[0]< value:
            self.mxq.popleft()  #左边pop
        self.mxq.appendleft(value)

    def pop_front(self) -> int:
        if not self.q:
            return -1
        res = self.q.popleft()
        if res == self.mxq[-1]:
            self.mxq.pop()
        return res

提交结果：