LeetCode 剑指 Offer 59 - II. 队列的最大值
目录
题目描述
题意分析
要设计一个队列类，对外提供三个方法：
push_back从队尾入队、pop_front从队头出队并返回被弹出的值、max_value返回当前队列中的最大值。队列为空时后两个方法都返回-1。
题面明确要求三个方法的均摊时间复杂度都是 $O(1)$。这条约束是整道题的分水岭：如果只要求正确，
max_value里遍历一遍队列就完事了；正是「均摊 $O(1)$」逼着我们把最大值信息预先维护起来，而不是每次现算。注意措辞是「均摊」而不是「最坏」，这暗示允许某一次操作花较多时间，只要总代价能摊平——这几乎是在明示解法里会有一个「批量弹出」的循环。
队列的先进先出特性带来一个比栈更难的地方。栈里维护最小值只需同步压入「到当前为止的最小值」，因为出栈总是撤销最近一次操作；而队列删除的是最早进来的元素，它可能恰好是当前最大值，删掉之后新的最大值来自哪里，不能靠简单的同步栈还原。所以必须换一套结构，让它随时知道「队头元素被移除后，谁是下一个最大值」。
另一个信号是「返回最大值」而不是「返回并删除最大值」——只查询不修改，说明这个辅助结构只需要保证队头正确，内部顺序如何不影响对外语义，这给了压缩存储的空间。
边界要盯住三处：空队列时
max_value与pop_front都返回-1；队列中可能有重复的最大值，出队一个不代表最大值就该消失；元素可能是任意 32 位整数，不能用-1之类的哨兵混在真实数据里判断。
解法：普通队列 + 单调队列
核心思路
普通队列能在 $O(1)$ 时间入队、出队，却要遍历才能求最大值。为使查询也达到均摊 $O(1)$，额外维护一个从队头到队尾单调不增的候选队列
maxDeque，其队头始终是当前最大值。淘汰依据是：若新值
value大于队尾候选x，那么x比value更早出队；只要x还在真实队列里，value也一定还在且更大，因此x永远不会成为最大值，可以删除。不变量：
maxDeque是真实队列的一个单调不增子序列，并保留所有仍可能成为最大值的元素。入队时删除队尾所有严格小于新值的候选；出队时，只有弹出值等于候选队头才同步删除。相等值不能淘汰，否则弹出一份最大值后会丢失仍在队列中的另一份。
解题步骤
max_value：候选队列为空返回-1，否则返回队头。push_back(value)：用while删除maxDeque队尾所有小于value的元素，再把value加入真实队列和候选队列。pop_front：真实队列为空返回-1；否则弹出队头，若它等于maxDeque队头，再同步弹出一份候选。例如依次入队
1, 3, 3, 2，候选队列变化为[1] → [3] → [3,3] → [3,3,2]。弹出1不影响候选；再弹出一个3时只删除候选队头的一份，最大值仍为3。
代码实现
import java.util.ArrayDeque;
import java.util.Deque;
class MaxQueue {
private final Deque<Integer> queue = new ArrayDeque<>();
private final Deque<Integer> maxDeque = new ArrayDeque<>();
public MaxQueue() {
}
public int max_value() {
return maxDeque.isEmpty() ? -1 : maxDeque.peekFirst();
}
public void push_back(int value) {
while (!maxDeque.isEmpty() && maxDeque.peekLast() < value) {
maxDeque.pollLast();
}
maxDeque.offerLast(value);
queue.offerLast(value);
}
public int pop_front() {
if (queue.isEmpty()) {
return -1;
}
int value = queue.pollFirst();
if (value == maxDeque.peekFirst()) {
maxDeque.pollFirst();
}
return value;
}
}
type MaxQueue struct {
queue []int
maxDeque []int
}
func Constructor() MaxQueue {
return MaxQueue{}
}
func (this *MaxQueue) Max_value() int {
if len(this.maxDeque) == 0 {
return -1
}
return this.maxDeque[0]
}
func (this *MaxQueue) Push_back(value int) {
for len(this.maxDeque) > 0 && this.maxDeque[len(this.maxDeque)-1] < value {
this.maxDeque = this.maxDeque[:len(this.maxDeque)-1]
}
this.maxDeque = append(this.maxDeque, value)
this.queue = append(this.queue, value)
}
func (this *MaxQueue) Pop_front() int {
if len(this.queue) == 0 {
return -1
}
value := this.queue[0]
this.queue = this.queue[1:]
if value == this.maxDeque[0] {
this.maxDeque = this.maxDeque[1:]
}
return value
}
复杂度分析
- 时间复杂度：三个方法的均摊复杂度都是 $O(1)$。单次入队最坏会删除 $O(n)$ 个候选，但每个元素只会进入和离开
maxDeque一次。- 空间复杂度：$O(n)$。真实队列与候选队列最多各保存 $n$ 个元素。
关键点总结
- 单调队列只保存仍可能成为最大值的元素，队头始终是答案。
- 新来的更大元素更晚出队，因此可淘汰它前面的较小候选。
- 清理条件必须是严格小于，以保留重复最大值的每一份。
while虽有线性最坏情况，但每个元素只被删除一次，因此整体是均摊常数时间。
易错点总结
- 清理条件写成
<=：连续入队两个3后只留一份候选，弹出第一个3就会丢掉仍有效的最大值。- 只用
if清理一次：候选为[5,4,3]时入队6，只删除3会留下非单调的[5,4,6]。- 出队时无条件删除候选队头：弹出的普通元素可能早已不在候选队列中，会误删真正的最大值。
- 忘记同步删除最大值：最大值离开真实队列后，查询仍会返回过期值。
- 空队列直接取队头：应按题意返回
-1，否则 Java 抛异常、Go 切片越界。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 239. 滑动窗口最大值 | 困难 | 同一套单调队列，但出队由窗口左边界驱动，队列里存下标而非值 |
| 剑指 Offer 59 - I. 滑动窗口的最大值 | 困难 | 与 239 同题，是本题作为「设计类」问题的算法原型 |
| 862. 和至少为 K 的最短子数组 | 困难 | 单调队列作用在前缀和上且允许负数，弹出条件同时来自「更优」与「已满足」两侧 |
| 155. 最小栈 | 中等 | 删除发生在栈顶，同步栈即可，用来对照为什么队列不能照搬这套做法 |
| 716. 最大栈 | 困难 | 除查询外还要删除最大元素，同步栈失效，需要有序结构配合双向链表 |
| 622. 设计循环队列 | 中等 | 纯队列结构设计，重点在定长数组上的头尾指针与空满判定 |
| 918. 环形子数组的最大和 | 中等 | 展开成两倍长度后可用单调队列维护定长窗口内的前缀和最小值 |
| 面试题 03.02. 栈的最小值 | 简单 | 与 155 同题，可直接套用同步栈写法 |