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

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

思路：

两个队列，一个维护最大值，一个正常插入

代码：

class MaxQueue {
public:
    MaxQueue() {

    }
    
    int max_value() {
        return q2.empty() ? -1 : q2.front();
    }
    
    void push_back(int value) {
        q1.push(value);
        while(!q2.empty() && q2.back() <= value) q2.pop_back();
        q2.push_back(value); 
    }
    
    int pop_front() {
        if(q1.empty()) return -1;
        int value = q1.front();
        q1.pop();
        if(q2.front() == value) q2.pop_front();
        return value;
    }
    queue<int> q1;
    //单调队列 从小到大
    deque<int> q2;
};

/**
 * 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();
 */