描述：

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

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

示例 1：

输入:
[“MaxQueue”,”push_back”,”push_back”,”max_value”,”pop_front”,”max_value”]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

示例 2：

输入:
[“MaxQueue”,”pop_front”,”max_value”]
[[],[],[]]
输出: [null,-1,-1]

限制：

1 <= push_back,pop_front,max_value的总操作数 <= 10000
1 <= value <= 10^5

代码模版：

class MaxQueue {
public:
    MaxQueue() {

    }

    int max_value() {

    }

    void push_back(int value) {

    }

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

思路:入队出队肯定是O(1)，问题是求最大值。
这里用到单调队列。

解决max_value()问题:

构造一个递减队列：back入队，front出队。

  • 当新元素new_item小于队头: 从back方向入队

  • 当新元素new_item大于队头: 先从back方向把所有小于new_item的数据弹出，再从back方向new_item入队

这样可以保证队列递减，并且弹出的数据均不可能是所求最大值。

还需要解决pop的问题：因为从back端弹出的数据不能再从front端弹出了。

我采用的是插入负数来记录弹出的数据数量。

比如[5,6,-2,8,9],”-2”指代两个被弹出的数据。(原始数据有可能是[5,6,1,2,8,9]这样子。。)

但pop是有返回值的，所以干脆就又加了一个普通链表(deque也可以)。。

class MaxQueue {
public:
    int *ptr;
    int head;
    int rear;
    list<int> res;
    MaxQueue() {
        ptr = new int[10000];
        head = 0;
        rear = 0;
    }

    int max_value() {
        if(head == rear) return -1;
        if(ptr[head] < 0)return ptr[head+1];
        return ptr[head];
    }

    void push_back(int value) {
        res.push_back(value);
        if(head == rear){
            ptr[rear++] = value;
            return;
        }
        if(value < ptr[rear-1]) ptr[rear++] = value; 
        else{
            int counter = 0;//counter记录了舍弃的元素个数
            while((head < rear) && ptr[rear-1] <= value){
                if(ptr[rear-1] < 0) counter += ptr[rear-1];
                else counter -= 1;
                --rear;
            }
            ptr[rear++] = counter;
            ptr[rear++] = value;
        }
        return;
    }

    int pop_front() {
        if(head == rear)
        return -1;
        int tmp = res.front();
        res.pop_front();
        if(ptr[head] <= -1)//正好有空缺
        {
            if(ptr[head] == -1){
                ++head;
                return tmp;
            }
            ++ptr[head];
            return tmp;
        }

        ++head;
        return tmp;
    }
};

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