剑指 Offer 59 - II. 队列的最大值

• 解题思路
• 代码

解题思路

这个需要翻译一下题目，不然题目比较难懂。

3、  "push_back"  向队列传入元素
        [2]                  传入的值为2
        此时队列为    [1,2] 
        函数无输出，故输出为null

4、   "max_value" 求队列中的最大值
        []                    传入的值为空
      						  输出为2

5、   "pop_front"   删除队列头部元素
        []                    传入的值为空
        函数pop_front还要输出删除元素的值，故输出为2

6、   "max_value" 求队列中的最大值
        []                    传入的值为空
         此时队列为[1]，所以最大值输出为1。

---

其实本质上是一个求滑动窗口最大值的问题。这个队列可以看成是一个滑动窗口，入队就是将窗口的右边界右移，出队就是将窗口的左边界右移。

既然是求解滑动窗口的最大值问题，那就变成了模板题，直接套单调队列模板即可。

代码

class MaxQueue {
        private Queue<Integer> queue;
        private Deque<Integer> deque;//用来维护一个递减队列，便于快速找到最大值

        public MaxQueue() {
            queue = new LinkedList<>();
            deque = new LinkedList<>();
        }

        public int max_value() {
            //deque的首元素就是最大值
            return deque.isEmpty() ? -1 : deque.peekFirst();
        }

        public void push_back(int value) {
            queue.offer(value);
            while (!deque.isEmpty() && deque.peekLast() < value) {
                deque.pollLast();
            }
            deque.offerLast(value);
        }


        public int pop_front() {
            if (queue.isEmpty()) {
                return -1;
            }
            //弹出的是最大值则两个都需要更新
            if (queue.peek().equals(deque.peekFirst())) {
                deque.pollFirst();
            }
            return queue.poll();
        }
    }

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