文章目录

• 1. 题目
• 2. 思路
• • (1) 单调双端队列
• 3. 代码

1. 题目

2. 思路

(1) 单调双端队列

• 利用一个正常队列执行正常的入队出队操作，利用一个单调递减的双端队列执行获取最大值的操作。

• 每次加入元素时，不仅要加入正常队列的队尾，还要加入单调队列的队尾，这样才能保证正常队列中的最大值处于单调队列中，而为了保证单调队列单调递减的性质，需要将单调队列队尾小于该元素的元素全部弹出，此时，单调队列的队头元素是正常队列中的最大值，后面的元素均是在最大值后面入队的单调递减的元素。

• 以正常队列[1,1,2,3,2,1,2]为例，此时的单调队列应该是[3,2,2]，若正常队列的出队元素等于单调队列的队头元素，则单调队列也需要出队，保证单调队列内的值是正常队列内已有的值。

3. 代码

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class Test {
    public static void main(String[] args) {
    }
}

class MaxQueue {
    private Queue<Integer> queue;
    private Deque<Integer> deque;

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

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

    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()) {
            int res = queue.poll();
            if (deque.peekFirst() == res) {
                deque.pollFirst();
            }
            return res;
        }
        return -1;
    }
}