0

我正在使用Deque来实现单调队列。我知道这Deque可以由ArrayDeque和创建LinkedList。这是我构建的 Monotonic 类：

public static class MonotonicQueue {
    Deque<Integer> monotonicQueue;

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

    void push(int n) {
        while (!monotonicQueue.isEmpty() && monotonicQueue.getLast() < n) {
            monotonicQueue.removeLast();
        }
        monotonicQueue.addLast(n);
    }

    int max() {
        return monotonicQueue.getFirst();
    }

    void pop(int n) {
        if (!monotonicQueue.isEmpty() && n == monotonicQueue.getFirst()) {
            monotonicQueue.removeFirst();
        }
        monotonicQueue.addLast(n);
    }
}

但是，问题出现在void push(int n)方法中，即删除所有为 的元素< n，然后将其添加n到尾部的队列中。我在一个方法中初始化了一个变量window，然后尝试推送一个元素来更新这个单调队列。

MonotonicQueue window = new MonotonicQueue();
window.push(3);

但它甚至无法插入第一个元素。奇怪的是，当我在构造函数中使用第二种方式时，说LinkedList<>而不是ArrayDeque，它工作得很好，即可以成功插入3。

public MonotonicQueue() {
    monotonicQueue = new LinkedList<>();
}

我想知道为什么一种方法有效，而另一种方法无效。这里发生了什么？谢谢！

4

0 回答 0