写出单调队列的java代码

### 回答1：

Deque<Integer> deque = new LinkedList<>();
for(int i=0; i<n; i++){
int num = scanner.nextInt();
while(!deque.isEmpty() && deque.getLast() > num){
deque.removeLast();
}
deque.addLast(num);
}
System.out.println(deque.getFirst());

### 回答2：
单调队列（Monotonic Queue）是一种特殊的队列数据结构，它具有以下特点：
1. 队列中的元素满足一定的单调性，例如单调递增或单调递减；
2. 每次插入一个新的元素时，会将队列中比新元素小的元素删除；
3. 队列中的元素按插入的顺序排列。

以下是用Java编写的单调队列的代码：

import java.util.*;

public class MonotonicQueue {
    Deque<Integer> deque; // 可以用双端队列来实现单调队列

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

    // 向队尾插入元素，删除比新元素小的元素
    public void push(int num) {
        while (!deque.isEmpty() && deque.getLast() < num) {
            deque.removeLast(); // 删除队尾元素
        }
        deque.addLast(num); // 插入新元素到队尾
    }

    // 返回队列中的最大元素
    public int getMax() {
        return deque.getFirst(); // 队头元素始终是最大值
    }

    // 删除队头元素
    public void pop() {
        deque.removeFirst();
    }
}

上述代码中，我们使用了Java的双端队列（Deque）来实现单调队列。在插入新元素时，我们不断地将队列中比新元素小的元素删除，以保持队列的单调性。同时，我们可以通过调用`getMax()`方法获取队列中的最大元素，通过调用`pop()`方法删除队头元素。

使用单调队列的时间复杂度为O(n)，其中n为元素个数。

### 回答3：
单调队列是一种特殊的队列，可以高效地找到队列中的最大或最小值。下面是一个使用Java实现的单调队列的代码示例：

import java.util.ArrayDeque;
import java.util.Deque;

public class MonotonicQueue {
    private Deque<Integer> queue; // 存储队列中的元素
    private Deque<Integer> maxElements; // 存储单调队列中的最大值

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

    public void push(int val) {
        while (!maxElements.isEmpty() && maxElements.peekLast() < val) {
            maxElements.pollLast(); // 如果当前值比最大值大，则移除最大值
        }
        maxElements.offerLast(val); // 将当前值加入最大元素队列
        queue.offerLast(val); // 将当前值加入原始队列
    }

    public void pop() {
        // 如果要移除的元素是最大元素，也要从最大元素队列中移除
        if (queue.peekFirst().equals(maxElements.peekFirst())) {
            maxElements.pollFirst();
        }
        queue.pollFirst(); // 移除原始队列中的第一个元素
    }

    public int getMax() {
        return maxElements.peekFirst(); // 返回最大元素队列中的第一个元素
    }

    public static void main(String[] args) {
        MonotonicQueue queue = new MonotonicQueue();
        queue.push(3);
        queue.push(5);
        queue.push(2);
        System.out.println(queue.getMax()); // 输出 5
        queue.pop();
        System.out.println(queue.getMax()); // 输出 5
        queue.pop();
        System.out.println(queue.getMax()); // 输出 2
    }
}

在上述代码中，我们使用`ArrayDeque`作为队列的实现，分别维护了`queue`和`maxElements`两个队列。`push`方法用于往队列中添加元素，其中使用了一个`while`循环来将队列中所有小于当前值的元素移除，保持队列的单调性。`pop`方法用于移除队列中的元素，如果要移除的元素是最大元素，则需要同时从最大元素队列中移除。`getMax`方法用于返回当前队列中的最大值。在`main`方法中，我们展示了单调队列的基本使用。