题解 | #滑动窗口的最大值#

思路：

思路1：首先想到的是暴力法，对每个窗口进行遍历，找到其最大值，在此基础上进行优化，并不会每次都遍历窗口，只有在左边界等于最大值时才重新遍历窗口，即代码1。

思路2：在利用指针遍历窗口时，发现指针遍历有3中可能。

1. 若遍历位置i的值大于i-1的值，则i-1位置的值便无存在的意义，因为若i-1还在窗口，则最大值已经不可能是i-1位置的值，若i-1不在窗口（因为位置i-1总是比位置i先出窗口），则位置i-1同样不可能是窗口中的最大值
2. 但若位置i的值小于i-1，则位置i的值应该保留，这样位置i-1出窗口后最大值可能是位置i的值，不会丢失下一个窗口的最大值；
3. 若位置i的值等于位置i-1的值，则保留位置i，丢掉保存的i-1，因为i-1比i先出窗口，而且两者的值相等。

综上，采用单调队列解答此题，队列保存的是索引的位置，根据上面总结的特点得出是单调递减队列，对应代码2。

注意点：

1. 注意丢掉在窗口外的左边界值，即左窗口到当前位置的长度大于等于size。
2. 注意什么时候应该加入res结果队列，当右边界>size-1时。

代码：

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        //思路2，单调队列
        ArrayList<Integer> res=new ArrayList<>();
        Deque<Integer> list=new LinkedList<>();
        for(int r=0,len=num.length;r<num.length;r++){
            if(list.isEmpty()){
                list.addLast(r);
            }else if(r-list.peekFirst()+1>size){
                list.removeFirst();
            }
            while(!list.isEmpty()&&num[r]>=num[list.peekLast()]){
                list.removeLast();
            }
            list.addLast(r);
            if(r-size+1>=0){//当右边界大于size-1时，每移动一次都要添加一个值
                res.add(num[list.peekFirst()]);
            }
        }
        return res;
//         //思路1，暴力法的优化，只有在左边界等于最大值时才重新遍历窗口
//         ArrayList<Integer> res=new ArrayList<>();
//         int l=0,r=0;
//         int maxNum=num[r];
//         for(;r<size;r++){
//             maxNum=Math.max(maxNum,num[r]);
//         }
//         res.add(maxNum);
//         while(r<num.length){
//             if(num[l]==maxNum){
//                 maxNum=num[l+1];
//                 for(int i=l+2;i<=r;i++){
//                     maxNum=Math.max(maxNum,num[i]);
//                 }
//             }
//             maxNum=Math.max(maxNum,num[r]);
//             r++;
//             l++;
//             res.add(maxNum);
//         }
//         return res;
    }
}