科技匠|Offer 59 - II. 队列的最大值 - leetcode 剑指offer系列，剑指题目难度:中等

题目难度:中等
原题链接[1]
今天继续更新剑指offer系列,老样子晚上6点45分准时更新公众号每日精选算法题,大家记得关注哦~另外在公众号里回复offer就能看到剑指offer系列当前连载的所有文章了
题目描述请定义一个队列并实现函数max_value得到队列里的最大值，要求函数max_value、push_back和pop_front的均摊时间复杂度都是O(1) 。
若队列为空， pop_front和max_value需要返回-1
1<=push_back,pop_front,max_value的总操作数<=100001<=value<=10^5题目样例示例输入:["MaxQueue","push_back","push_back","max_value","pop_front","max_value"][[],[1],[2],[],[],[]]输出:[null,null,null,2,1,2]输入:["MaxQueue","pop_front","max_value"][[],[],[]]输出:[null,-1,-1]题目思考要做到均摊时间复杂度为O(1),需要哪些数据结构?解决方案思路一个比较容易想到的思路是使用一个双端队列模拟,然后每次利用max函数求最大值,但这样求最大值的时间复杂度为O(N),不满足题目要求如果我们能够动态维护当前队列的最大值,那么求最大值的时候只需要用O(1)时间返回这个值即可但只使用一个变量来保存最大值并不够用,因为当它被pop的时候必须重新计算新的最大值,时间复杂度仍为O(N)所以需要把当前队列的第二大值,第三大值...也都给保存下来上面的分析是不是和昨天的题目剑指Offer59-I.滑动窗口的最大值-leetcode剑指offer系列很类似?没错,我们仍然需要把这些值保存在一个单调双端队列中,一边是最小值,一边是最大值,大家可以结合昨天的文章一起阅读这里采用单调队列左侧最小右侧最大的方案,各个操作具体细节如下:max_value:直接返回单调队列右侧最大值即可,不存在则返回-1push_back:将新元素加到正常队列左侧,且从单调队列左侧不断弹出比新元素更小的值,最后将新元素插入单调队列左侧作为新的最小值,因为更小的值绝不可能是最大值候选项了(更小且更旧)pop_front:弹出并返回正常队列右侧元素,不存在则返回-1;且如果单调队列最大值恰好等于弹出的元素时,也需要将其从单调队列中弹出下面代码对必要的步骤有详细的解释,特别是对push_back和pop_front的一些关键点的解释,方便大家理解复杂度时间复杂度O(1):显然max_value和pop_front操作的复杂度都是O(1).而对于push_back操作,虽然它使用了while循环,可能弹出多个元素,但是每个元素只会进入和弹出单调队列各一次,所以整个操作序列下来的均摊时间复杂度为O(1)空间复杂度O(N):队列需要存所有值代码classMaxQueue:def__init__(self):#使用两个deque,一个存正常的队列,另一个存单调队列#正常的队列self.q=collections.deque()#单调队列,左边小,右边大self.monoq=collections.deque()defmax_value(self)->int:ifnotself.monoq:return-1#直接返回最大值returnself.monoq[-1]defpush_back(self,value:int)->None:#将新元素加到正常队列左侧self.q.appendleft(value)#保证新的值是最小值,因为更小的值绝不可能是最大值候选项了(更小且更旧)#注意这里不能是<=,那样的话如果当前新值也恰好是最大值,<=的话就会把原来已经有的的最大值错误的弹出,这样会导致后面的最大值计算出现错误,只会统计1个最大值,而不是原来的若干个whileself.monoqandself.monoq[0]int:ifnotself.q:return-1#弹出正常队列最右侧元素res=self.q.pop()#如果最右侧元素恰好也是最大值的话,也从单调队列中弹出它#注意这里最右侧元素只能有两种情况:是最大值或者不在单调队列中#因为如果最右侧元素存在于单调队列且不是最大值时,那么说明它在正常队列左侧的元素中存在比它大的,那根据上面的push_back操作,左侧的那个最大值一定会把这个最右侧元素给淘汰掉,而不会留它在单调队列中,与假设矛盾,所以这种情况不成立ifres==self.monoq[-1]:self.monoq.pop()returnres参考资料[1]