力扣-面试题59-II，队列的最大值【Python】

LeetCode面试题59-II.队列的最大值[Medium][Python][Queue]请定义一个队列并实现函数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]限制:1<=push_back,pop_front,max_value总操作数<=100001<=value<=10^5idea辅助队列sort_queheadofqueueAlways队列的最大值。时间复杂度：O(1)Python3codefromcollectionsimportdequeclassMaxQueue:def__init__(self):self.que=deque()self.sort_que=deque()defmax_value(self)->int:returnself.sort_que[0]ifself.sort_queelse-1defpush_back(self,value:int)->None:self.que.append(value)#sort_que:non-increasingnon-increasingwhileself.sort_queandself.sort_que[-1]int:如果不是self.que:return-1res=self.que.popleft()#popleft():O(1),pop(i):O(n)ifres==self.sort_que[0]:self.sort_que.popleft()returnres#你的MaxQueue对象将被实例化并这样调用：#obj=MaxQueue()#param_1=obj.max_value()#obj.push_back(value)#param_3=obj.pop_front()代码地址GitHub链接参考【Python】详解：为什么可以通过增加辅助队列实现O(1)操作？