单调递增队列的实现

Question

我正在尝试使用 Java 双端队列接口和 LinkedList class。假设我有一个 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

单调队列

单调队列可以增加或减少。

In a Monotonic Increasing Queue, when a new element e is pushed, every queue's element q[i] that violates the condition q[i] >= e, starting from the lowest element, is popped out of the queue.

同样

In a Monotonic Decreasing Queue, when a new element e is pushed, every queue's element q[i] that violates the condition 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]

总之，回答你的问题：

am I supposed to have {1, 2, 3, 8} or just {3, 8}?

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

单调递增队列的实现

Implementation for a Monotonic Increasing Queue

java

arrays

algorithm

queue

linked-list

单调队列

示例单调递增队列

示例单调递减队列

回答