题目描述
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}。
针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下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]}。

  在每个滑动窗口依次比较找出最大值，每进来一个数循环比较一次，然后窗口会移动n次，时间复杂度是O(nk)。所以需要进行优化，有很多方式实现，比如队列来记录，或者使用堆。

解法1：

蛮力法

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size){
        ArrayList<Integer> result = new ArrayList<>();
        if(num == null || size > num.length || size == 0)
           return result;
        int first = 0;
        int last = first+size-1;
        for(int n = 0; n < num.length - size + 1; n++){
            getMax(num,result,first,last);
            first++;
            last++;
        }
//改成while可以省一个变量，因为n和first同步变化
        //while(first < num.length - size + 1){
        //  getMax(num,result,first,last);
        //   first++;
        //   last++;
        //}
       return result; 
    }
 //获取最大值的方法可以根据个人喜好选择
    public void getMax(int [] num,ArrayList<Integer> result, int first, int last) {
        int i = first;
        int tmp = num[first];
        while(i<last){
            if(tmp<num[i+1])
                tmp = num[i+1];//如果这个数比较小，那么就更新成和它相比，比较大的数
            i++;
        }
        result.add(tmp);
    }
}

解法2：

　　不管是建立堆还是队列或者其他方法，都需要保证使用的数据结构里面是有序的。其实也是一种排序的优化。在第一个窗口移动前，需要保证这个窗口已经有序，所以在调整窗口前需要先排序。整个队列其实是从大到小排列的。
　　思路：建立一个两端开口的队列，放置所有可能是最大值的数字（存放的其实是最大值的下标），队首记录的是最大值的下标。从头开始扫描数组：

  • 1.如果遇到的数字比队列中所有的数字都大，那么它就是最大值，其它数字不可能是最大值了，将队列中的所有数字清空，放入该数字。（在尾部添加的）
  • 2.如果遇到的数字比队列中的所有数字都小，那么它还有可能成为之后滑动窗口的最大值，放入队列的末尾
  • 3.如果遇到的数字比队列中最大值小，最小值大，那么将比它小数字不可能成为最大值了，删除较小的数字，放入该数字。
  • 其中1和3可以放在一起处理，代码复用。
  • 由于滑动窗口有大小，因此，队列头部的数字如果其下标离滑动窗口末尾的距离大于窗口大小，那么也删除队列头部的数字。

  这么说的可能还是有点抽象，以题目给的例子分析，{2,3,4,2,6,2,5,1}及滑动窗口的大小3。第一个窗口的过程是，队列变成{2}，3比2大，队列为{3}，同理，4进入后，队列变成{4}。注意，队列的尾部的4就是第一个窗口最大值，应该添加到res中。（为了方便起见，下列分析中，队列中写的是数字，在实际代码中，队列中的是对应数字在整个数组中的索引）
  第二个窗口进来了2，将2和4比较，发现4大，说明第二窗口最大还是4，将4添加到res，2添加到队列中，队列变成{4,2}。
  第三个窗口进来了6，6比队首的4还大，清空队列，添加6到队列，队列{6}，添加6到res。
  第四个窗口，2进来了，res添加6，队列变成{6,2}。
  第五个窗口进来5，5比2大，比6小。res添加队首6，队列变成{6,5}。
  最后一个窗口进来1，注意，6不在最后一个窗口中了，此时应该删除队首。而1也进不去队列，队列为{5}，res添加5。因此res中添加的顺序就是4,4,6,6,6,5。
  在最后一个窗口进来1时，6应当被移出去，所以我们需要记录每一个进来的元素的索引，否则我们就不知道队首什么时候有效，什么时候失效，这就是队列中不存放元素，而存放对应元素的角标的原因。

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size){
        ArrayList<Integer> res = new ArrayList<>();
        Deque<Integer> deque = new LinkedList<>();
        if(size <= 0 || size > num.length){
            return res;
        }
        for (int i = 0; i < size; i++) {//在第一个窗口中，挑出最大的数，并记录该数的角标
            while (!deque.isEmpty() && num[deque.peekLast()] < num[i]){
                deque.pollLast();
            }
            deque.addLast(i);
        }
        res.add(num[deque.peekFirst()]);//第一个窗口已经比较完了，添加操作。

        for (int i = size; i < num.length; i++) {
            if (num[i] < num[deque.peekLast()]){//小于就直接添加到队列（注意比较的是队尾）
                deque.addLast(i);
            }else {//这个写法将大于或等于的两种情况合并成了一种写法
                while (!deque.isEmpty() && num[i] >= num[deque.peekLast()]){
                    deque.pollLast();
                }
                deque.addLast(i);
            }
            while (deque.peekLast() - deque.peekFirst() >= size){//如果太长，要删掉队首
                deque.pollFirst();
            }
            res.add(num[deque.peekFirst()]);//删掉队首后，可以放心的添加了
        }
        return res;
    }
}

解法3：

heap的方法也值得自己去学习。摘过来某位大佬的写法

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
           ArrayList<Integer> list=new ArrayList<>();
        if(size==0||size>num.length){
            return list;
        }
        PriorityQueue<Integer>  maxheap=new PriorityQueue<>
                        (size,new Comparator<Integer>(){
           @Override
           public int compare(Integer o1, Integer o2) {
               return o2-o1;
           }
       });

        int z=0;
        for(int i=0;i<size;i++){
            maxheap.add(num[i]);
        }
        for(int i=size;i<num.length;i++){
            list.add(maxheap.peek());
            maxheap.remove(num[z++]);
            maxheap.add(num[i]);
        }
        list.add(maxheap.peek());
        return list;
    }
}

总结：

有一说一，第二种是书上的方法，第一次接触这个题，这个解法不太容易想到。可以看到第2，3种解法都是使得窗口已经有序，这样就避免每更新一个值时，需要操作很多次，所以这题也是考察了一下排序的优化。