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

题目

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

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

示例：

  1. 输入: 
  2. ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
  3. [[],[1],[2],[],[],[]]
  4. 输出: [null,null,null,2,1,2]
输入: 
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]

解答 & 代码

单调队列（用双端队列实现）：

class MaxQueue {
private:
    deque<int> monotonicQ;    // 单调队列（用双端队列实现）
    queue<int> dataQ;        // 数据队列，存储所有插入的元素
public:
    MaxQueue() {
    }

    int max_value() {
        return monotonicQ.empty() ? -1 : monotonicQ.front();
    }

    void push_back(int value) {
        dataQ.push(value);    // 在数据队列尾部插入 value
        // 在单调队尾插入元素 value，插入前先将前面比 value 小的元素都删除
        while(!monotonicQ.empty() && monotonicQ.back() < value)
            monotonicQ.pop_back();
        monotonicQ.push_back(value);
    }

    int pop_front() {
        int front = dataQ.empty() ? -1 : dataQ.front();
        if(!dataQ.empty())
            dataQ.pop();
        if(!monotonicQ.empty() && front == monotonicQ.front())
            monotonicQ.pop_front();
        return front;
    }
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */

复杂度分析：假设一共插入 N 个元素

  • 时间复杂度：插入、删除、求最大值的均摊时间复杂度都是 O(1)
    • 插入操作虽然有个循环，一次插入操作可能会有 n 次弹出，但是总体来看每个数字只会出队一次，因此均摊时间复杂度还是 O(1)
  • 空间复杂度 O(N)：dataQ 队列存储所有插入的元素
执行结果：通过

执行用时：108 ms, 在所有 C++ 提交中击败了 60.79% 的用户
内存消耗：47.6 MB, 在所有 C++ 提交中击败了 64.37% 的用户