《剑指 Offer》第 59 题：队列的最大值

题目链接：剑指 Offer 59 - II. 队列的最大值 (opens new window)：

• 首先指出这个问题的方法是需要学习的；

• 要求队列的最大值，需要把一些数据存起来，怎么存、怎么取，需要找规律；

• 先写 queue 的操作，再写 deque 的操作，写 deque 的操作的时候对着图片；

• 重要的例子：[8, 6, 5] 接下来要进来 7，有 7 在 5、6 肯定不是队列的最大值；

• 如果队列中的元素从「队首」到「队尾」是单调递减（单调不增）的，这些元素都要被保留，因为 如果出队，它们都有可能是队列中的最大元素；

• 一旦来了一个「严格增加」的元素，需要把「严格小于」它们的元素全部拿出去；

• 原始的数据队列也需要记录下来，这是因为要比较当前出队的元素是不是最大元素；

• 双端队列，不是队列，是队首可以出队，队尾可以入队也可以出队的线性数据结构。

  把各种特殊的情况用 PPT 画出来。

讲解代码的时候，先写框架：

class MaxQueue {

    // 只使用队列的 API
    private Queue<Integer> queue;

    // 可以使用双端队列的 API，允许队首出队
    private Deque<Integer> temp;

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

    public int max_value() {

    }

    public void push_back(int value) {
        queue.offer(value);
    }

    public int pop_front() {
        if (queue.isEmpty()) {
            return -1;
        }

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

再写实现细节：

• 注意 1：return queue.poll();

• 注意 2：add 的时候，queue 和 temp 需要同步加 temp.addLast(value);

class MaxQueue {

    // 只使用队列的 API
    private Queue<Integer> queue;

    // 可以使用双端队列的 API，允许队首出队
    private Deque<Integer> temp;

    public MaxQueue() {
        queue = new ArrayDeque<>();
        temp = new ArrayDeque<>();
    }

    public int max_value() {
        if (temp.isEmpty()) {
            return -1;
        }
        return temp.peekFirst();
    }

    public void push_back(int value) {
        queue.offer(value);

        while (!temp.isEmpty() && temp.peekLast() < value) {
            temp.removeLast();
        }
        temp.addLast(value);
    }

    public int pop_front() {
        if (queue.isEmpty()) {
            return -1;
        }

        // 这里不能用「==」
        if (queue.peek().equals(temp.peekFirst())) {
            temp.removeFirst();
        }
        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();
 */

参考代码：

class MaxQueue {

    private Queue<Integer> queue;
    private Deque<Integer> deque;

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

    public int max_value() {
        if (queue.isEmpty()) {
            return -1;
        }
        return deque.peekFirst();
    }

    public void push_back(int value) {
        queue.offer(value);
        while (!deque.isEmpty() && value > deque.peekLast()) {
            deque.removeLast();
        }
        deque.addLast(value);
    }

    public int pop_front() {
        if (queue.isEmpty()) {
            return -1;
        }
        if (queue.peek().equals(deque.peekFirst())) {
            deque.removeFirst();
        }
        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();
 */

---

作者：liweiwei1419 链接：https://suanfa8.com/queue/solutions/dui-lie-de-zui-da-zhi-lcof 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。