剑指 Offer 59 - II. 队列的最大值(中等)

发布时间 2023-07-31 22:41:55作者: 孜孜不倦fly

题目:

class MaxQueue {
public:
    deque<int> que1;      //使用两个双端栈(deque和queue不一样,用deque就行)
    deque<int> que2;
    MaxQueue() {

    }
    
    int max_value() {
        return que2.empty()?-1:que2.front();
    }
    
    void push_back(int value) {
        que1.push_back(value);
        while(!que2.empty()&&que2.back()<value){        //que2维护为单调递减栈,栈头为最大值
            que2.pop_back();
        }
        que2.push_back(value);
    }
    
    int pop_front() {
        if(que2.empty())return -1;
        int max=que1.front();
        que1.pop_front();
        if(que2.front()==max){           //如果que1中的弹出值等于que2栈头,那么que2才弹出栈头
            que2.pop_front();
        }
        return max;
    }
};