剑指 Offer 59 - II. 队列的最大值

剑指 Offer 59 - II. 队列的最大值

解法一

  • 均摊时间复杂度O(1)
  • 空间复杂度O(n)
  • 题目是队列，所以先进先出，所以当插入最大值时，可以删除之前的值，因为后面插入的总是后删除
class MaxQueue {

    private Deque<Integer> list;
    private Deque<Integer> max;

    public MaxQueue() {
        list = new LinkedList<>();
        max = new LinkedList<>();
    }

    public int max_value() {
        return list.isEmpty()? -1: max.peekFirst();
    }

    public void push_back(int value) {
        list.offerLast(value);
        while (!max.isEmpty() && value > max.peekLast()) {
            max.pollLast();
        }
        max.offerLast(value);
    }

    public int pop_front() {
        if (list.isEmpty()) {
            return -1;
        }
        int pop = list.pop();
        if (max.peekFirst() == pop) {
            max.pop();
        }
        return pop;
    }
}

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue obj = new MaxQueue();
 * int param_1 = obj.max_value();
 * obj.push_back(value);
 * int param_3 = obj.pop_front();
 */