[Lc]面试题59_II队列的最大值

题目


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

题解

添加一个辅助的递减双端队列，用来保存对应队列中该数的最大值 push时：
当新添加的数小于队列中的所有值时，直接添加即可
当新添加的数大于队列的后几个值时，需要将队列中小的数挨个取出，再放入新数

pop时：
当要取出的数等于当前的最大值时，两个队列都弹出队首的值
当要取出的数不等于当前的最大值时，原队列弹出队首的值，辅助队列不变
返回原队列的队首

时间复杂度$O(1)$（均摊）
空间复杂度$O(n)$

class MaxQueue {//一个方法。1.辅助递减双端队列 
    queue<int> q;
    deque<int> max_d;//用于存最大值的辅助单调双端队列
public:
    MaxQueue() {

    }
    
    int max_value() {
        //直接返回递减双端队列的队首
        if(max_d.empty()) return -1;
        return max_d.front();
    }
    
    void push_back(int value) {
        //判断当前加入的值是否大于双端队列队尾的值
        //若大于，就把队尾小于该值的数挨个剔除
        //接着压入新数，即从上一个最大值到当前次大值之间的最大值都是该次大值
        //同时原队列压入新值
        while(!max_d.empty() && value > max_d.back()){
            max_d.pop_back();
        }
        q.push(value);
        max_d.push_back(value);
    }
    
    int pop_front() {
        if(q.empty()) return -1;
        int res = q.front();//先暂存要pop出的值
        //若要pop的值等于当前的最大值，说明最大值已经取出
        //保存最大值的双端队列弹出该值
        if(max_d.front() == res){
            max_d.pop_front();
        }
        //原队列弹出该值
        //返回结果
        q.pop();
        return res;
    }
};

Contents

题目

题解