LeetCode刷题 【剑指 Offer 59-II】队列的最大值

请定义一个队列并实现函数 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

题解

思路和上一题【239】滑动窗口最大值类似，单调队列

根据题面，我们必然需要维护一个队列用来从尾部插入新值，从头部弹出旧的值。接下来的问题就是怎么维护这个最大值，且这个最大值在从头部弹出后需要自动维护到比他小的一个值。所以这边就想到了用一个有序集合来维护这个大小排序的关系。

同样的因为题面中的单向性，只从尾部新增，只从头部弹出，且只需要维护一个最大值的情况。可以试想下这样的场景，我们在依次从集合头部弹出数值，而此时的的最大值关系我们可以知道从头部到最大值之间的关系是不需要维护的。

而当最大值弹出的时候，我们只需要知道从最大值的位置到末尾的位置之间的最大值即可。那么思路就自然出来了。

import java.util.LinkedList;

//leetcode submit region begin(Prohibit modification and deletion)
class MaxQueue {

    private LinkedList<Integer> maxValueList = new LinkedList<>();

    private LinkedList<Integer> queue = new LinkedList<>();

    public MaxQueue() {

    }

    //取最大值
    public int max_value() {
        if (!maxValueList.isEmpty()){
            return maxValueList.getFirst();
        }
        return -1;
    }
    //往尾添加一个
    public void push_back(int value) {
        queue.addLast(value);
        while (!maxValueList.isEmpty() && maxValueList.getLast() <= value){
            maxValueList.pollLast();
        }
        maxValueList.addLast(value);
    }
    //从头部弹出
    public int pop_front() {
        if (queue.isEmpty()){
            return -1;
        }
        if (queue.peekFirst().equals(maxValueList.getFirst())){
            maxValueList.pollFirst();
        }
        return queue.pollFirst();
    }
}

/**
 * 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();
 */
//leetcode submit region end(Prohibit modification and deletion)