本文共 1077 字，大约阅读时间需要 3 分钟。

题目

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

思路

再用一个队列来实现存最大值，因为只用一个int值来存最大值的话，出队的时候就不知道次大值了

这篇题解质量很高，易懂：

代码

class MaxQueue {public:    queue
   
     q;    deque
    
      dq;    MaxQueue() {    }        int max_value() {        if(dq.size() == 0)            return -1;        return dq.front();    }        void push_back(int value) {        q.push(value);        if(dq.size() == 0){            dq.push_back(value);        }else{            while(dq.size() != 0 && dq.back() < value){                dq.pop_back();            }            dq.push_back(value);        }            }        int pop_front() {        if(q.size() == 0){            return -1;        }        int res = q.front();        if(dq.front() == res){            dq.pop_front();        }        q.pop();        return res;    }};/** * 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(); */
    
   

转载地址：https://blog.csdn.net/hanmin822/article/details/106113272 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！