单调递增队列的实现

Question

我正在尝试使用 Java Deque 接口和 LinkedList 类实现快速单调严格递增队列。假设我有一个 int 数组 {10, 7, 1, 2, 4, 3, 8}，对其执行单调队列后，我应该有 {1, 2, 3, 8} 还是只是 {3, 8}？

根据我的实现，我有 {1, 2, 3, 8}。

附上我的代码：

import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;

/**
 * A Strictly Monotonic increasing Queue. [1, 2, 3, 6, 8, 12, 16, 23]. Where the largest element is
 * at the back of the Queue (tail of the linkedList).
 * Adapter Design Pattern.
 */
public class MonotonicQueue<E extends Object & Comparable<E>> implements Iterable<E> {

    private final Deque<E> queue;
    private int t = 0;                          // Number of elements in the Queue

    public MonotonicQueue() {
        this.queue = new LinkedList<>();
    }

    private void nullChecker(E obj) {
        if (obj == null)
            throw new NullPointerException();
    }

    public int size() {
        return t;
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }

    public void push(E obj) {
        nullChecker(obj);
        if (isEmpty())
            queue.offerFirst(obj);
        else {
            while(!queue.isEmpty() && queue.peekLast().compareTo(obj) >= 0) {
                queue.pollLast();
                t--;
            }
            queue.offerLast(obj);
        }
        t++;
    }

    public E pop() throws EmptyQueueException {
        if (isEmpty())
            throw new EmptyQueueException();
        t--;
        return queue.pop();            // This will return the maximum element (The front element) in the Queue
    }

    public boolean contains(E obj) {
        if (obj == null)
            return false;
        if (isEmpty())
            return false;

        // If obj > the element at the front of the Queue, then the Queue cannot contain obj.
        else if (obj.compareTo(queue.peekLast()) > 0)
            return false;
        else {
            for (E data : this) {
                if (data.compareTo(obj) == 0)
                    return true;
            }
        }
        return false;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder("[");
        Iterator<E> iter = this.iterator();
        while (iter.hasNext()) {
            stringBuilder.append(iter.next());
            if (iter.hasNext())
                stringBuilder.append("--> ");
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

    @Override
    public Iterator<E> iterator() {
        return queue.iterator();
    }
}

提前致谢。

Answer 1

单调队列

单调队列可以是递增或递减。

在单调递增队列中，当新元素 e 被压入时，每个队列中违反条件 q[i] >= e 的元素 q[i] 都会从最低元素开始弹出队列。

同样

在单调递减队列中，当新元素 e 被压入时，每个队列的元素 q[i] 都会违反条件 q[i] <= e, starting from the lowest element, is popped out of the queue.

单调递增队列示例

5 => [5]
3 => [3] 3 弹出 5
1 => [1] 1 弹出 3
2 => [1, 2]
4 => [1, 2, 4]

单调递减队列示例

5 => [5]
3 => [5, 3]
1 => [5, 3, 1]
2 => [5, 3, 2] 2 弹出 1
4 => [5, 4] 4 弹出 2, 3

回答

在您的情况下，我假设您尝试获取的单调队列正在增加，因此根据您给定的数组 {10, 7, 1, 2, 4, 3, 8}，在每次迭代时我们都会有:

10 => [10]
7 => [7]
1 => [1]
2 => [1, 2]
4 => [1, 2, 4]
3 => [1, 2, 3]
8 => [1, 2, 3, 8]

总之，回答你的问题：

我应该有 {1, 2, 3, 8} 还是只有 {3, 8}？

你应该获得 {1, 2, 3, 8}。