JZ64：滑动窗口的最大值

解法1：暴力求解

public static ArrayList<Integer> maxInWindows(int[] nums,int size){
        ArrayList<Integer> res=new ArrayList<>();
        int len=nums.length;
        if(size==0 || size>len){
            return res;
        }
        for(int i=0;i<=len-size;i++){
            int max=nums[i];
            for(int j=i+1;j<size+i;j++){
                if(nums[j]>max){
                    max=nums[j];
                }
            }
            res.add(max);
        }
        return res;
    }

解法2：双向队列

• 如果不考虑时间开销，使用蛮力法，本题并不难解决，依次遍历所有的滑动窗口，扫描每个窗口中的所有数字并找出其中的最大值，这都很容易实现，但是如果滑动窗口的大小为k，那么需要O(k)的时间找最大值，对于长度为n大的数组，总的时间复杂度为O(nk)。 
• 然后我们考虑进一步优化，一个滑动窗口实际上可以看成一个队列。当窗口滑动时，处于窗口第一个位置的数字被删除，同时在窗口的末尾又增加了一个新的数字。这符合队列“先进先出”的特性。
  使用双端队列。我们不把所有的值都加入滑动窗口，而是只把有可能成为最大值的数加入滑动窗口。这就需要一个两边都可以操作的双向队列。
    我们以数组{2,3,4,2,6,2,5,1}为例，滑动窗口大小为3，先把第一个数字2加入队列，第二个数字是3，比2大，所以2不可能是最大值，所以把2删除，3存入队列。第三个数是4，比3大，同样删3存4，此时滑动窗口以遍历三个数字，最大值4在队列的头部。
    第4个数字是2，比队列中的数字4小，当4滑出去以后，2还是有可能成为最大值的，因此将2加入队列尾部，此时最大值4仍在队列的头部。
    第五个数字是6，队列的数字4和2都比它小，所以删掉4和2，将6存入队列尾部，此时最大值6在队列头部。
    第六个数字是2，此时队列中的数6比2大，所以2以后还有可能是最大值，所以加入队列尾部，此时最大值6在仍然队列头部。
    ······
    依次进行，这样每次的最大值都在队列头部。
    还有一点需要注意的是：如果后面的数字都比前面的小，那么加入到队列中的数可能超过窗口大小，这时需要判断滑动窗口是否包含队头的这个元素，为了进行这个检查，我们可以在队列中存储数字在数组中的下标，而不是数值，当一个数字的下标和当前出来的数字下标之差大于等于滑动窗口的大小时，这个元素就应该从队列中删除。
  

  import java.util.*;
  public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> res = new ArrayList<>();
        if(num.length==0 || size<=0 || size>num.length){
            return res;
        }
        LinkedList<Integer> maxqueue=new LinkedList<Integer>();
        for(int i=0;i<num.length;i++){
            while(!maxqueue.isEmpty() && num[maxqueue.peekLast()]<num[i]){
                maxqueue.pollLast();
            }
            maxqueue.addLast(i);
            if(maxqueue.peekFirst()==i-size){
                maxqueue.pollFirst();
            }
            if(i>=size-1){
                res.add(num[maxqueue.peekFirst()]);
            }
        }
        return res;
    }
  }

解法3：用大顶堆实现滑动窗口最大值查询

用一个大顶堆，保存当前滑动窗口中的数据。滑动窗口每次移动一格，就将前面一个数出堆，后面一个数入堆。

public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>((o1,o2)->o2.compareTo(o1));
        ArrayList<Integer> res=new ArrayList<Integer>();
        if(num.length==0 || size<=0 || size>num.length){
            return res;
        }
        //初始化滑动窗口
        for(int i=0;i<size;i++){
            maxHeap.add(num[i]);
        }
        res.add(maxHeap.peek());
        //对每次操作，找到最大值（用优先队列的大顶堆），然后向后滑动（出堆一个，入堆一个）
        int count=size;
        while(count<num.length){
            maxHeap.remove(num[count-size]);
            maxHeap.add(num[count]);
            count++;
            res.add(maxHeap.peek());
        }
        return res;
    }
}