讨论/《图解算法数据结构》 - 剑指 Offer 59 - II. 队列的最大值/
《图解算法数据结构》 - 剑指 Offer 59 - II. 队列的最大值
class MaxQueue {
    deque<int> record;
    queue<int> dq;
public:
    MaxQueue() {
        dq={};
        record={};
    }
    
    int max_value() {
        if(!record.empty())
        {
            return record.front();
        }
        else
        {
            return -1;
        }
    }
    
    void push_back(int value) {
        if(record.empty()||value<record.back())
        {
            record.push_back(value);
            dq.push(value);
            return ;
        }
        while(!record.empty()&&record.back()<value)
        {
            record.pop_back();
        }
        record.push_back(value);
        dq.push(value);
    }
    int pop_front() {
        if(dq.empty())
        {
            return -1;
        }
        if(!record.empty()&&dq.front()==record.front())
        {
            record.pop_front();
        }
        int temp=dq.front();
        dq.pop();
        return temp;
    }
};
/**
 * 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();
 */
展开全部 18 讨论