剑指offer：滑动窗口的最大值
题目描述
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}。
思路：
1.暴力**法：可以扫描每一个滑动窗口的所有数字并找出其中的最大值。如果滑动窗口的大小为k，需要O(k)时间才能找出滑动窗口里的最大值。对于长度为n的输入数组，这个算法总的时间复杂度是O(nk)。
2.最大堆：用最大堆存储滑动窗口中的数值，每次可以以o(1)的时间获得最大值。
3.双向队列：实际上一个滑动窗口可以看成是一个队列。当窗口滑动时，处于窗口的第一个数字被删除，同时在窗口的末尾添加一个新的数字。这符合队列的先进先出特性。如果能从队列中找出它的最大数，这个问题也就解决了。
不必每个窗口的每个数都存下来，我们用一个双向队列deque来存储，注意：我们在这存的是数组元素的索引
（1）如果新来的值比队列尾部的数小，那就追加到后面，因为它可能在前面的最大值划出窗口后成为最大值
（2）如果新来的值比尾部的大，那就删掉尾部（因为有更大的在后面，所以它不会成为最大值，划出也是它先划出，不影响最大值），再追加到后面，循环下去直到小于
（3）如果追加的值比的索引跟队列头部的值的索引超过窗口大小，那就删掉头部的值
其实这样每次队列的头都是最大的那个
图示：
参考：
https://blog.csdn.net/u010429424/article/details/73692248
https://cuijiahua.com/blog/2018/02/basis_64.html
实现1：双向队列
import java.util.ArrayList;
import java.util.LinkedList;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size)
{
ArrayList<Integer> ret=new ArrayList<Integer>();
if(num==null||num.length==0||size==0||size>num.length){
return ret;
}
LinkedList<Integer> queue=new LinkedList<Integer>();
for(int i=0;i<num.length;i++){
if(!queue.isEmpty()){
//如果队首值超过滑动窗口的范围
if(i>=queue.peek()+size){
queue.pop();//删除队头
}
while(!queue.isEmpty()&&num[i]>num[queue.getLast()]){
//如果新来的值大于队尾的值，则删除队尾
queue.removeLast();
}
}
queue.offer(i);
if(i+1>=size){
ret.add(num[queue.peek()]);
}
}
return ret;
}
}
实现2：借助优先队列
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size)
{
ArrayList<Integer> ret=new ArrayList<Integer>();
if(num==null||num.length==0||size==0||size>num.length){
return ret;
}
PriorityQueue<Integer> queue=new PriorityQueue<Integer>(11,new Comparator<Integer>(){
@Override
public int compare(Integer o1,Integer o2){
return o2.compareTo(o1);
}
});
int time=-1;
for(int i=0;i<num.length;i++){
queue.offer(num[i]);
if(queue.size()==size){
time++;
int max=queue.poll();
ret.add(max);
queue.clear();
i=time;
}
}
return ret;
}
}参考：