题目描述

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

示例 1：

输入:
[“MaxQueue”,”push_back”,”push_back”,”max_value”,”pop_front”,”max_value”]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
示例 2：

输入:
[“MaxQueue”,”pop_front”,”max_value”]
[[],[],[]]
输出: [null,-1,-1]

解题思路

• 使用一个sort_que 排序的辅助队列。通过该队列记录插入列表的最大值排序。

代码

from collections import deque
class MaxQueue:
    def __init__(self):
        self.sort_que = deque()
        self.que = deque()
    def max_value(self) -> int:
        if self.sort_que:
            return self.sort_que[0]
        return -1

    def push_back(self, value: int) -> None:
        if  len(self.que) == 0:
            self.sort_que.append(value)
            self.que.append(value)
            return 
        if value > self.sort_que[0]:
            self.sort_que = deque()
            self.sort_que.append(value)
            self.que.append(value)            
            return 
        while self.sort_que[-1] < value:
            self.sort_que.pop()
        self.sort_que.append(value)
        self.que.append(value)


    def pop_front(self) -> int:
        if self.que:
            v = self.que.popleft()
            if v == self.sort_que[0]:
                self.sort_que.popleft()
            return v
        return -1