59.队列的最大值（中等）

考点：本题考查队列和知识迁移能力

题目一描述：滑动窗口的最大值

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，{[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}，他们的最大值分别为{4,4,6,6,6,5}

思路：双端队列

建立一个两端开口的队列，用来保存有可能是滑动窗口最大值的数字的下标。在存入一个数字的下标之前，首先要判断队列里已有数字是否小于待存入的数字。如果已有的数字小于待存入的数字，那么这些数字已经不可能是滑动窗口的最大值，因此它们将会被依次从队列的尾部删除（调用函数.removeLast()）。同时，如果队列头部的数字已经从窗口里滑出（队列头部的数字如果其下标离滑动窗口末尾的距离大于窗口大小），那么滑出的数字也需要从队列的头部删除（调用函数.removeFirst()）。由于队列的头部和尾部都有可能删除数字，这是需要两端开口的队列的原因。

import java.util.ArrayList;
import java.util.ArrayDeque;//ArrayDeque类提供了可调整大小的阵列
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> result = new ArrayList<>();
        if(num == null||num.length <= 0||size <= 0||size > num.length)
            return result;
        //队列中存放的是数组下标
        ArrayDeque<Integer> indexDeque = new ArrayDeque<Integer>();
        for(int i=0;i<size-1;i++){
            while(!indexDeque.isEmpty() && num[i]> num[indexDeque.getLast()])
                indexDeque.removeLast();
            indexDeque.addLast(i);
        }
        for(int i=size-1;i<num.length;i++){
            while(!indexDeque.isEmpty() && num[i]> num[indexDeque.getLast()])
                indexDeque.removeLast();
            if(!indexDeque.isEmpty() && (indexDeque.getFirst()<=(i-size)))
                indexDeque.removeFirst();
            indexDeque.addLast(i);
            result.add(num[indexDeque.getFirst()]);
        }
     return result;
    }
}

ArrayDeque双端队列常用的方法

ArrayDeque.png

题目二描述：队列的最大值

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
输入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

思路：双端队列同上

class MaxQueue {
    private ArrayDeque<Integer> valueDeque = new ArrayDeque<Integer>() ;
    private ArrayDeque<Integer> maxValueDeque = new ArrayDeque<Integer>() ;
    public MaxQueue() {
    }
    
    public int max_value() {
        if(!maxValueDeque.isEmpty())
            return maxValueDeque.peek();
        return -1;
    }
    
    public void push_back(int value) {
        valueDeque.addLast(value) ;
        while (!maxValueDeque.isEmpty() && maxValueDeque.getLast() < value) {
            maxValueDeque.pollLast() ;
        }
        maxValueDeque.addLast(value) ;
    }
    
    public int pop_front() {
        if (valueDeque.isEmpty())
            return -1 ;
        else{
            int result = valueDeque.pollFirst() ;
            if (result == maxValueDeque.peek())
                maxValueDeque.pollFirst() ;
            return result ;
        }
    }
}

/**
 * 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();
 */