剑指 Offer 59 - II. 队列的最大值（单调队列）

待我称王封你为后i 2022-11-25 04:14 111阅读 0赞

请定义一个队列并实现函数 max\_value 得到队列里的最大值，要求函数max\_value、push\_back 和 pop\_front 的均摊时间复杂度都是O(1)。

若队列为空，pop\_front 和 max\_value 需要返回 -

思路：  
首先，要保存所有压入的数字，因为pop时返回值，其次，维护最大值当前：但是基于队列的性质，保证先进先出，所以当后面进入的数字，能够影响到此时的最大值的只有前面的比他大的数，所以这就是天然的单调队列的时候，在每次压入的时候，都将小于该数的弹出，然后就维护了一个递减队列。

数据结构：deque（双端开口队列）  
queue（底层是deque的先进先出队列）

code

class MaxQueue { 
    private:
        queue<int> nums;
       deque<int> iq;
        int maxV;
        //单调队列可以满足,单调递减
    public:
        MaxQueue() { 
        }
        
        int max_value() { 
            if(iq.empty())
                return -1;
            return iq.front();
        }
        
        void push_back(int value) { 
            while(!iq.empty() && value> iq.back())
                    iq.pop_back();
            iq.push_back(value);
            nums.push(value);
            return ;
        }
        
        int pop_front() { 
            if(iq.empty())
                return -1;
            if(iq.front()==nums.front()){ 
                iq.pop_front();         //弹出前一个
            }
            int front=nums.front();
            nums.pop();
            return front;
        }
    };
    
    /** * 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(); */