题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}

实现方法

• 采用双端队列，队列头部永远存储扫描过的数字的最大值（队列存储数组中的下标不存储值）
• 具体做法：分两段扫描，0-size和size-num.length
• 第一段表示的是第一个窗口，后面是每次扫描一个数字加入窗口中进行判断
• 以数组{2,3,4,2,6,2,5,1}为例子，数组的第一个数字是2，把它存入队列中。第二个数字是3，比2大，所以2不可能是滑动窗口中的最大值，因此把2从队列里删除，再把3存入队列中。第三个数字是4，比3大，同样的删3存4。此时滑动窗口中已经有3个数字，而它的最大值4位于队列的头部。
• 第四个数字2比4小，但是当4滑出之后它还是有可能成为最大值的，所以我们把2存入队列的尾部。下一个数字是6，比4和2都大，删4和2，存6。就这样依次进行，最大值永远位于队列的头部。
• 但是我们怎样判断滑动窗口是否包括一个数字？应该在队列里存入数字在数组里的下标，而不是数值。当一个数字的下标与当前处理的数字的下标之差大于或者相等于滑动窗口大小时，这个数字已经从窗口中滑出，可以从队列中删除

• 具体的输入表格如下图中所示

  
  示意过程图https://cuijiahua.com/blog/2018/02/basis_64.html

java源代码

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> result = new ArrayList<>();
        if (num==null || num.length==0 || size<=0 || num.length < size) return result;
        LinkedList<Integer> queue = new LinkedList<>();
        for(int i=0; i<size; i++) {
            while(!queue.isEmpty()&&num[i]>=num[queue.getLast()]) queue.removeLast();
            queue.add(i);
        }
        for (int i=size; i<num.length; i++) {
            result.add(num[queue.getFirst()]);
            while(!queue.isEmpty()&&num[i]>=num[queue.getLast()]) queue.removeLast();
            if(!queue.isEmpty()&&queue.getFirst()<=(i-size)) {
                queue.removeFirst();
            }
            queue.add(i);
        }
        result.add(num[queue.getFirst()]);
        return result;
    }
}

参考链接

https://cuijiahua.com/blog/2018/02/basis_64.html