队列的最大值

题目来源：剑指offer59

今天发一道剑指offer上面的经典题目，主要考察面试者的知识迁移能力，下面我们先来看一下题目描述。

请定义一个队列并实现函数 max_value 得到队列里的最大值，若队列为空，pop_front(出队操作) 和 max_value (获取队列最大值)需要返回 -1

示例 1：

输入: ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"] [[],[1],[2],[],[],[]] 输出: [null,null,null,2,1,2]

示例 2：

输入: ["MaxQueue","pop_front","max_value"] [[],[],[]] 输出: [null,-1,-1]

输入的第一行代表的执行函数，第二行代表的是输入的值，该题中只有我们的push_back传入了参数，输出代表的为执行该函数时，函数的返回值。

个人认为这个题目还是很不错的，而且也有一定的难度，大家可以试着实现一下。

为保证严谨性，文章中的所有代码都经过测试，大家可以放心食用

暴力解法

暴力法，是因为我们的max值通过每次遍历我们的动态数组来获得。思路很简单，我们创建一个动态数组，我们每次执行max_value函数时，通过遍历数组获得最大值，入队操作则用add,出队操作则用remove(0)，去除动态数组的头元素。

题目代码：

class MaxQueue {
    //动态数组
    ArrayList arr =  new ArrayList<>();
    public MaxQueue() {
       
    }       
    public int max_value() {
         //为空的情况
         if(arr.size() == 0){
           return -1;
         }
         //初始化max
         int max = Integer.MIN_VALUE;
         //遍历动态数组，获取最大值
         for(int i = 0;i            
            if(arr.get(i)>max){
               max = arr.get(i);
            }

         }
             return max;

    }

    public void push_back(int value) {
        //添加元素
        arr.add(value);   

    }

    public int pop_front() {
        //队列为空时，执行该函数返回-1
       if(arr.size() == 0){
           return -1;
       }else{   
           return arr.remove(0);
       }
      
    }
    
}

利用双端队列

deque （double-ended queue，双端队列）是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。

我们了解了双端队列之后，是不是感觉很实用，很灵活，但实际上在应用程序中远不及栈和队列有用。我们了解双端队列之后，我们来聊一下我们的做题思路吧

这个思路也很简单，我们充分利用双端队列的性质，因为它可以两头出队，那我们在双端队列中仅保存队列中每一段的最大值即可，见下图。

我们分成了三段，第一段的最大值为9，第二段为8，第三段为7。那么我们这个段是怎么分的呢？

我们看第一段最大值为9前面没有其他数字，第二段最大值为8，前面的三个数字都小于8，但是它小于第一段的最大值，同理第三段也是。如果第三段的元素为6，10的话，那我们的双端队列中只有10啦，因为它大于它之前的所有值。

废话不多说下面我们直接看动图吧。

题目代码：

class MaxQueue {

    Queue queue ;
    
    Deque deque;
    public MaxQueue() {
        queue = new LinkedList();
        
        deque = new LinkedList();

    }   
    //返回最大值，此时返回的为depue的第一个元素
    public int max_value() {
        if(deque.isEmpty()){
            return -1;
        }
        int max = deque.getFirst();
        return max;
    }
    
    //入队操作
    
    public void push_back(int value) {
    
        //普通队列直接入队
        
        queue.offer(value);
        
        //双端队列需要先将该阶段小于value值的出队
        
        while( !deque.isEmpty() && deque.getLast() < value){
          deque.removeLast();
        }
        
        //入队value
        
        deque.offer(value);
        
    }
    
    //出队操作，返回两种情况，队头小于当前阶段最大值，队头等于当前阶段最大值
    
    public int pop_front() {
        if(queue.isEmpty()){
            return -1;
        }
        
        //普通队列出队
        
        int temp = queue.poll();
        
        //判断普通队列和双端队列的队头是否相等，两种返回情况
        if(temp == deque.peekFirst()){
            return deque.pollFirst();
        }
        else{
           return  temp;
        }

    }
}