本系列導航：劍指offer（第二版）java實現(xiàn)導航帖

面試題59.2：隊列的最大值

題目要求：
定義一個隊列并實現(xiàn)函數(shù)max得到隊列里的最大值浮禾。要求max，pushBack燕鸽，popFront的時間復雜度都是o(1)。

解題思路：
兩個思路均延續(xù)自59.滑動窗口的最大值
思路1：借助之前做過的9.用兩個棧實現(xiàn)隊列和30.包含min函數(shù)的棧，我們可以實現(xiàn)求隊列的最大值菜皂。入隊時間復雜度o(1)，出隊時間復雜度o(n),獲取最大值時間復雜度o(1)厉萝，空間復雜度o(n)恍飘。

思路2：將上一題的滑動窗口看成一個隊列即可榨崩。入隊時間復雜度o(1)，出隊時間復雜度o(1)章母，調整記錄下標的雙端隊列的時間復雜度最差為o(n)母蛛，獲取最值得時間復雜度為o(1)。

思路2的代買實現(xiàn)如下：

package chapter6;

import java.util.*;

/**
 * Created with IntelliJ IDEA
 * Author: ryder
 * Date  : 2017/8/19
 * Time  : 13:46
 * Description: 隊列的最大值
 **/
public class P292_QueueWithMax {
    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;
            public 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(5);
        System.out.println(queue.max());
        queue.pushBack(1);
        System.out.println(queue.max());
        System.out.println("開始出隊后乳怎，調用max");
        System.out.println(queue.max());
        queue.popFront();
        System.out.println(queue.max());
        queue.popFront();
        System.out.println(queue.max());
        queue.popFront();
        System.out.println(queue.max());


    }
}

運行結果

3
5
5
開始出隊后彩郊，調用max
5
5
1
null