剑指 Offer 59 - II. 队列的最大值 #
- 标签:设计、队列、单调队列
- 难度:中等
题目大意 #
要求:设计一个「队列」,实现 max_value
函数,可通过 max_value
得到大年队列的最大值。并且要求 max_value
、push_back
、pop_front
的均摊时间复杂度都是 O(1)
。
解题思路 #
利用空间换时间,使用两个队列。其中一个为原始队列 queue
,另一个为递减队列 deque
,deque
用来保存队列的最大值,具体做法如下:
push_back
操作:如果deque
队尾元素小于即将入队的元素value
,则将小于value
的元素全部出队,再将valuew
入队。否则直接将value
直接入队,这样deque
队首元素保存的就是队列的最大值。pop_front
操作:先判断deque
、queue
是否为空,如果deque
或者queue
为空,则说明队列为空,直接返回-1
。如果都不为空,从queue
中取出一个元素,并跟deque
队首元素进行比较,如果两者相等则需要将deque
队首元素弹出。max_value
操作:如果deque
不为空,则返回deque
队首元素。否则返回-1
。
代码 #
|
|