队列的最大值

题目：

​ 请定义一个队列并实现函数max得到队列里的最大值，要求函数max、push_back和pop_front的时间复杂度都是O(1)。

分析：

​ 将上一题的滑动窗口看成一个队列即可。入队时间复杂度o(1)，出队时间复杂度o(1)，调整记录下标的双端队列的时间复杂度最差为o(n)，获取最值得时间复杂度为o(1)。

代码：

class MaxNumberSolution {

    public static class QueueWithMax<T extends Comparable>{

        private Deque<InternalData<T>> queueData;
        private Deque<InternalData<T>> queueMax;
        private int currentIndex;

        public QueueWithMax() {
            this.queueData = new ArrayDeque<>();
            this.queueMax = new ArrayDeque<>();
            this.currentIndex = 0;
        }

        public T max() {
            if (queueMax.isEmpty()) {
                return null;
            }
            return queueMax.getFirst().value;
        }

        public void pushBack(T value) {
            while (!queueMax.isEmpty() && value.compareTo(queueMax.getLast().value) >= 0) {
                queueMax.removeLast();
            }

            InternalData<T> addData = new InternalData<>(value, currentIndex);
            queueMax.addLast(addData);
            queueData.addLast(addData);
            currentIndex++;
        }

        public T popFront() {
            if (queueData.isEmpty()) {
                return null;
            }
            InternalData<T> delData = queueData.removeFirst();
            if (delData.index == queueMax.getFirst().index) {
                queueMax.removeFirst();
            }
            return delData.value;
        }
    }

    private static class InternalData<M extends Comparable>{
        public M value;
        private int index;

        public InternalData(M value, int index) {
            this.value = value;
            this.index = index;
        }
    }

    public static void main(String[] args) {
        QueueWithMax<Integer> queue = new QueueWithMax<>();
        queue.pushBack(3);
        System.out.println(queue.max());
        queue.pushBack(2);
        queue.pushBack(4);
        System.out.println(queue.max());
        queue.pushBack(1);
        System.out.println(queue.max());
        System.out.println(queue.popFront());
        System.out.println(queue.popFront());
        System.out.println(queue.popFront());
    }
}