算法1

(队列) $O(n)$

1. 先判断队列是否为空，如果为空，将当前的下标放进队列作为最大值;
2. start用来检测当前队列中的最大值是否已经离开滑动窗口，所以一开始start=i-k+1,如果start大于队列中最大值的下标，则弹出最大值
3. 然后判断队列是否为空，并且从队列尾与当前值比较，来更新队列中的最大值；
4. 当start。=0时，说明滑动窗口已经完全进入数组，可以开始记录最大值了

Java 代码

class Solution {
    public int[] maxInWindows(int[] nums, int k) {
        int[] res = new int[nums.length-k+1];
        if(k==0)return res;
        int start;
        int index = 0;
        ArrayDeque<Integer> max = new ArrayDeque<>();
        for(int i=0;i<nums.length;i++){
            start = i-k+1;
            if(max.isEmpty())
                max.add(i);
            else if(start>max.peekFirst())
                max.pollFirst();

            while((!max.isEmpty())&&nums[max.peekLast()]<=nums[i])
                max.pollLast();
            max.add(i);
            if(start>=0)
                res[index++] = nums[max.peekFirst()];
        }
        return res;
    }
}