1、队列的最大值

今天我们好好说说单调栈和单调队列。其实很容易理解，单调栈就是单调递增或单调递减的栈，栈内元素是有序的，单调队列同样也是。

下面我们通过几个题目由浅入深，一点一点挖透他们吧！

题目描述

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

请定义一个队列并实现函数 max_value 得到队列里的最大值

若队列为空，pop_front 和 max_value 需要返回 -1

示例 1：

输入: ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"] > [[],[1],[2],[],[],[]] 输出: [null,null,null,2,1,2]

示例 2：

输入: ["MaxQueue","pop_front","max_value"] > [[],[],[]] 输出: [null,-1,-1]

题目解析

我们先来拆解下上面的示例 1

队列的最大值

其实我觉得这个题目的重点在理解题意上面，可能刚开始刷题的同学，对题意理解不够透彻，做起来没有那么得心应手，通过上面的图片我们简单了解了一下题意，那我们应该怎么做才能实现上述要求呢？

下面我们来说一下双端队列。我们之前说过的队列，遵守先进先出的规则，双端队列则可以从队头出队，也可以从队尾出队。我们先通过一个视频来简单了解下双端队列。

我们可以用双端队列做辅助队列，用辅助队列来保存当前队列的最大值。我们同时定义一个普通队列和一个双端单调队列。普通队列就正常执行入队，出队操作。max_value 操作则返回咱们的双端队列的队头即可。下面我们来看一下代码的具体执行过程吧。

我们来对视频进行解析

1.我们需要维护一个单调双端队列，上面的队列则执行正常操作，下面的队列队头元素则为上面队列的最大值

2.出队时，我们需要进行对比两个队列的队头元素是否相等，如果相等则同时出队，则出队后的双端队列的头部仍未上面队列中的最大值。

3.入队时，我们需要维持一个单调递减的双端队列，因为我们需要确保队头元素为最大值嘛。

代码

class MaxQueue {
    //普通队列
    Queue<Integer> que;
    //双端队列
    Deque<Integer> deq;
    public MaxQueue() {
        que = new LinkedList<>();
        deq = new LinkedList<>();
    }
    //获取最大值值，返回我们双端队列的对头即可，因为我们双端队列是单调递减的嘛
    public int max_value() {
        return deq.isEmpty() ? -1 : deq.peekFirst();
    }
    //入队操作
    public void push_back(int value) {
        que.offer(value);
        //维护单调递减
        while (!deq.isEmpty() && value > deq.peekLast()){
            deq. pollLast();
        }
        deq.offerLast(value);

    }
    //返回队头元素，此时有个细节，我们需要用equals
    //这里需要使用 equals() 代替 == 因为队列中存储的是 int 的包装类 Integer
    public int pop_front() {
        if(que.isEmpty()) return -1;
        if (que.peek().equals(deq.peekFirst())) {
            deq.pollFirst();
        }
        return que.poll();
    }
}

C++ Code:

#include <queue> // 包含queue和deque
using namespace std;

class MaxQueue {
private:
    queue<int> que;       // 普通队列：存储所有元素
    deque<int> deq;       // 双端队列：维护单调递减序列（队头始终为当前最大值）

public:
    // 构造函数：初始化队列（C++默认构造函数已完成空队列初始化）
    MaxQueue() {}
    
    // 获取当前队列中的最大值
    int max_value() {
        // 双端队列为空时返回-1，否则返回队头元素（当前最大值）
        return deq.empty() ? -1 : deq.front();
    }
    
    // 入队操作
    void push_back(int value) {
        que.push(value); // 元素先加入普通队列
        
        // 维护双端队列的单调递减性：
        // 若双端队列非空，且当前元素大于队尾元素，则弹出队尾（这些元素不可能成为未来的最大值）
        while (!deq.empty() && value > deq.back()) {
            deq.pop_back();
        }
        // 将当前元素加入双端队列尾部（它可能是后续的最大值）
        deq.push_back(value);
    }
    
    // 出队操作
    int pop_front() {
        // 普通队列为空时返回-1
        if (que.empty()) {
            return -1;
        }
        
        // 获取普通队列的队头元素（即将弹出的元素）
        int frontVal = que.front();
        que.pop(); // 弹出普通队列的队头
        
        // 若弹出的元素是双端队列的队头（当前最大值），则双端队列也弹出队头（更新最大值）
        if (frontVal == deq.front()) {
            deq.pop_front();
        }
        
        return frontVal; // 返回弹出的元素
    }
};