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

传送门

leetcode

题目描述

请定义一个队列并实现以下函数：
get_max()：获取队列中的最大值。如果队列为空，则返回 -1
add(value)：将 value 加入队列的尾部。
remove()：移除第一个值。如果队列为空，则返回 -1
注意：以上函数的均摊时间复杂度均为 O(1)

C++ 代码 - leetcode

class Checkout {
public:
    Checkout() {

    }
    
    int get_max() {
        int res = -1;
        for (int i = begin; i != end; i++) {
            res = max(res, q[i]);
        }
        return res;
    }
    
    void add(int value) {
        q[end ++] = value;
    }
    
    int remove() {
        if (begin == end) return -1;
        return q[begin ++];
    }

private:
    int q[20000];
    int begin = 0, end = 0;
};

/*
    维护一个单调的双端队列
*/
class Checkout {
public:
    Checkout() {

    }
    
    int get_max() {
        if (dq.empty()) return -1;
        return dq.front();
    }
    
    void add(int value) {
        while (!dq.empty() && dq.back() < value) {
            dq.pop_back();
        }
        dq.push_back(value);
        que.push(value);
    }
    
    int remove() {
        if (que.empty()) return -1;
        int res = que.front();
        if (res == dq.front()) {
            dq.pop_front();
        }
        que.pop();
        return res;
    }

private:
    queue<int> que; // 队列
    deque<int> dq; // 单调队列
};