（面试题59 - II）队列的最大值

解题思路

主要思路:
常规的遍历求队列最大值的方法时间复杂度太高，不符合题意。因此可考虑使用一个辅助队列sup来保存队列中元素最大值的方法。具体实现方法是：如果sup不为空，并且sup的最后一位元素小于当前入队元素value的话，直接把最后一位元素弹出，直到sup为空，或sup的最后一位元素大于等于value。这就保证了sup是单调递减的，且sup的头部总是原始队列的最大值。

步骤：
1)初始化原始队列que和辅助队列sup；
2)求最大值，即辅助队列的首元素sup[0]；
3)入队，首先，在原始队列que末尾添加当前元素value；其次，对于辅助队列，如果sup不为空，并且sup的最后一位元素小于当前入队元素value的话，直接把最后一位元素弹出，直到sup为空，或sup的最后一位元素大于等于value，然后把value加入辅助队列。
4)出队，原始队列首元素出队，并将其与辅助队列的首元素比较，如果相同，辅助队列的首元素也出队，否则，只出队原始队列的首元素。

注：Python中的list形式，用pop(0)的方法可以弹出list的第一个元素，但时间复杂度是O(n)。因此这里采用了Python中的deque()，其可以用popleft()实现pop(0)，时间复杂度为O(1)。

复杂度分析
时间复杂度：O(1)（插入，删除，求最大值），删除操作于求最大值操作显然只需要 O(1) 的时间。而插入操作虽然看起来有循环，做一个插入操作时最多可能会有 n 次出队操作。但要注意，由于每个数字只会出队一次，因此对于所有的 n 个数字的插入过程，对应的所有出队操作也不会大于 n 次。因此将出队的时间均摊到每个插入操作上，时间复杂度为 O(1)。

空间复杂度：O(n)，需要用队列存储所有插入的元素。

代码

class MaxQueue:

    def __init__(self):
        from collections import deque
        self.queue = deque()
        self.queue_sup = deque() #辅助队列


    def max_value(self) -> int:
        if not self.queue_sup:
            return -1
        else:
            return self.queue_sup[0]


    def push_back(self, value: int) -> None:
        self.queue.append(value)
        while self.queue_sup and self.queue_sup[-1] < value:
            self.queue_sup.pop()
        self.queue_sup.append(value)


    def pop_front(self) -> int:
        if not self.queue_sup:
            return -1
        else:
            res = self.queue.popleft()
        if res == self.queue_sup[0]:
            self.queue_sup.popleft()
        return res



# Your MaxQueue object will be instantiated and called as such:
# obj = MaxQueue()
# param_1 = obj.max_value()
# obj.push_back(value)
# param_3 = obj.pop_front()