LeetCode 剑指 Offer 59 - II. 队列的最大值

约 5 分钟
文章信息 9 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 剑指 Offer 剑指 Offer（第 2 版） 字节 快手
标签
设计 队列 单调队列

题目描述

✅ 剑指 Offer 59 - II. 队列的最大值

image-20261001230752590

题意分析

实现先进先出的队列，支持尾部入队、头部出队，以及查询当前最大值。队列为空时，出队和查询最大值都返回 -1；每个操作要求均摊 $O(1)$ 时间。

只保存一个最大值不够，因为最大值出队后还需要知道剩余元素的最大值。需要额外保留未来仍可能成为最大值的候选，并及时淘汰不可能再用到的元素。

解法：普通队列 + 单调队列

核心思路

[!blue]

普通队列 queue 保存所有尚未出队的元素，保证先进先出。辅助双端队列 maxDeque 保存最大值候选：候选仍按入队先后排列，数值从队首到队尾单调不增，因此队首就是当前最大值。

入队一个新值 value 时，若候选队尾比它小，就可以删除旧候选。原因是新值更大，而且入队更晚；只要旧值尚未出队，新值就一定还在，旧值不可能再成为需要保留的最大值。不断删除严格较小的队尾后，再把新值加入末尾，就能维持单调性。这些删除只发生在候选队列，普通队列中的元素仍要按原顺序出队。

相等候选必须逐份保留。当前实现存的是值，没有下标或重复次数；如果删除旧的相等值，将来旧值出队时，就无法区分并可能误删新值对应的候选。因此清理队尾使用 < value，而不是 <= value。

出队时，先从普通队列取出最早元素。若它等于候选队首，就同步移除队首的一份候选；若它更小，说明它此前已被后来更大的值淘汰，无需修改候选队列。查询时直接读取候选队首，两个队列为空的状态会同步保持。

每个元素最多进入候选队列一次，也最多从队尾或队首离开一次。一次入队虽然可能连续淘汰很多候选，但这些候选之后不会再被处理，所以一串操作的总维护次数是线性的。

解题步骤

  1. 初始化普通队列和候选双端队列，二者都为空。
  2. push_back(value)：从候选队尾连续删除严格小于 value 的元素，再把 value 加入两个队列的尾部。
  3. pop_front()：普通队列为空就返回 -1；否则取出普通队首，若它等于候选队首，再从候选队首删除一份，最后返回该值。
  4. max_value()：候选队列为空就返回 -1，否则返回队首。

代码实现

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(1)$。单次入队最坏可能删除整个候选队列，但每个候选在全部操作中只进入和离开一次；底层动态数组扩容的开销也按均摊计算。
  • 空间复杂度：$O(q)$，q 是操作期间普通队列的规模峰值。候选队列是尚未出队元素的一个子序列，长度不会超过普通队列。

关键点总结

[!green]

  • 普通队列负责出队顺序，单调队列负责最大值候选，不能把被淘汰的候选也从普通队列删除。
  • 后来的较大值更晚离开，能覆盖旧的较小值在剩余生命周期内的最大值作用。
  • 存值的实现保留每份相等候选，出队时也只同步删除一份。
  • 均摊 $O(1)$ 依靠每个候选至多入队、出队各一次，不代表每次入队只弹出一个元素。

易错点总结

[!yellow]

  • 使用 <= 清理候选尾部，会丢失重复值对应的份数，之后可能过早删除仍在队列中的最大值。
  • 普通队列每次出队都无条件删除候选队首，会把与当前出队元素无关的最大值误删。
  • 只删除一个较小队尾而不用循环，可能留下破坏单调性的候选，队首也就不再保证是最大值。
  • 空队列直接取队首，会越界或访问空值；应按约定返回 -1。

相似题目

题目 难度 关联与区别
239. 滑动窗口最大值 困难 同样用单调队列保留最大值候选，原题按固定窗口自动过期，本题由pop_front决定过期时机。
155. 最小栈 中等 两题都给容器增加极值查询，但队列删除最早元素，栈删除最新元素，辅助状态维护不同。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/90693853
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！