Java中基于LinkedList的Deque如何以均摊O(1)时间实现max()方法？

核心思路是借助一个辅助双端队列maxDeque维护候选最大值，队列内元素保持单调递减顺序，这样队首始终是当前主Deque的最大值。每个元素在maxDeque中只会被添加和删除一次，因此所有操作的均摊时间复杂度为O(1)。

以下是各方法的具体实现逻辑：

1. 添加元素操作 #

addFirst(Integer x) #

• 先将x添加到主Deque的头部
• 遍历maxDeque的尾部，移除所有小于等于x的元素（这些元素不可能成为未来的最大值，因为x比它们大且会更晚被移除）
• 将x添加到maxDeque的尾部

addLast(Integer x) #

• 先将x添加到主Deque的尾部
• 遍历maxDeque的尾部，移除所有小于等于x的元素
• 将x添加到maxDeque的尾部

2. 删除元素操作 #

removeFirst() #

• 从主Deque头部移除元素，记为removed
• 如果removed等于maxDeque的队首元素，说明当前最大值被移除，需同步从maxDeque头部删除该元素
• 返回removed

removeLast() #

• 从主Deque尾部移除元素，记为removed
• 如果removed等于maxDeque的尾部元素，说明该元素是候选最大值之一，需同步从maxDeque尾部删除该元素
• 返回removed

3. max()方法 #

• 直接返回maxDeque的队首元素（需先判断主Deque是否为空，避免抛出空指针异常）

完整代码示例 #

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

public class MaxDeque {
    private Deque<Integer> deque;
    private Deque<Integer> maxDeque;

    public MaxDeque() {
        deque = new LinkedList<>();
        maxDeque = new LinkedList<>();
    }

    public void addFirst(Integer x) {
        deque.addFirst(x);
        // 移除maxDeque尾部所有小于等于x的元素
        while (!maxDeque.isEmpty() && maxDeque.getLast() <= x) {
            maxDeque.removeLast();
        }
        maxDeque.addLast(x);
    }

    public void addLast(Integer x) {
        deque.addLast(x);
        // 移除maxDeque尾部所有小于等于x的元素
        while (!maxDeque.isEmpty() && maxDeque.getLast() <= x) {
            maxDeque.removeLast();
        }
        maxDeque.addLast(x);
    }

    public Integer removeFirst() {
        if (deque.isEmpty()) {
            throw new IllegalStateException("Deque is empty");
        }
        Integer removed = deque.removeFirst();
        if (removed.equals(maxDeque.getFirst())) {
            maxDeque.removeFirst();
        }
        return removed;
    }

    public Integer removeLast() {
        if (deque.isEmpty()) {
            throw new IllegalStateException("Deque is empty");
        }
        Integer removed = deque.removeLast();
        if (removed.equals(maxDeque.getLast())) {
            maxDeque.removeLast();
        }
        return removed;
    }

    public Integer max() {
        if (deque.isEmpty()) {
            throw new IllegalStateException("Deque is empty");
        }
        return maxDeque.getFirst();
    }

    // 测试用例
    public static void main(String[] args) {
        MaxDeque md = new MaxDeque();
        md.addLast(3);
        md.addLast(1);
        md.addLast(4);
        System.out.println(md.max()); // 输出4
        md.removeLast();
        System.out.println(md.max()); // 输出3
        md.addFirst(5);
        System.out.println(md.max()); // 输出5
        md.removeFirst();
        System.out.println(md.max()); // 输出3
    }
}

内容的提问来源于stack exchange，提问作者Girly Girl