剑指offer59-Ⅱ 队列的最大值【设计、队列】
题目描述
请定义一个队列并实现函数 max_value
得到队列里的最大值,要求函数max_value
、push_back
和 pop_front
的均摊时间复杂度都是O(1)。
若队列为空,pop_front
和 max_value
需要返回 -1
示例 1:
1 | 输入: |
示例 2:
1 | 输入: |
限制:
1 <= push_back,pop_front,max_value的总操作数 <= 10000
1 <= value <= 10^5
解题思路
方法一:队列
使用双端队列来保存最大值,如果加入的值比双端队列的尾部大,则将尾部元素退出,尾部元素大于等于即将加入的值或者双端队列为空。
代码实现
1 | class MaxQueue { |
复杂度分析
max_value
、push_back
和pop_front
的均摊时间复杂度都是O(1)。空间复杂度:O(n)
资料
剑指offer59-Ⅱ 队列的最大值【设计、队列】
You need to set
install_url
to use ShareThis. Please set it in _config.yml
.