题目：
给定一个长度为 n 的数组 nums 和滑动窗口的大小 size ，找出每一个滑动窗口里数值中的最大值。
例如，如果输入数组{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]}。
隐含条件：双端队列，要保持单调递减，而当后进来的比先进来的都大了，那么先进去的那些就没有可能再成为最大，也就无用了！即当新加入元素比之前的还大时，直接弹出之前的元素！
思路：
用双端队列表示滑动窗口（先进先出的特性），注意队列存储的是下标而不是元素的大小！
- 清理： 清理窗口前面的元素，即过期元素(当队列头部元素索引 ≤ i-k时，弹出头部元素) ，以保持窗口宽度k
- 维护：用单调队列来维护滑动窗口（元素的大小单调递减），当不满足单调递减时就清理掉前面小的元素，使用while循环，直到队列单调递减（即新加入的元素要小于 队列尾部才能维持单调递减！若新加入的元素大于队列尾部，则直接弹出队列尾部！）
- 新元素的索引入队列
- 队列最左边的元素就是滑动窗口的最大值 ！每次返回最左边的元素即可
实现：
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int k) {
if(num.length==0||k==0){ // 安全校验
return null;
}
ArrayDeque<Integer> deque=new ArrayDeque<>(); //初始化双端队列
int n=num.length;
ArrayList<Integer> list=new ArrayList<>();
for(int i=0;i<n;i++){ // i是每轮新加入的索引
//注意队列存的是索引！不是元素大小
//1. 清除过期元素，当队列头部≤ i-k 则需要弹出 （要清除就要保证队列不为空）
while(!deque.isEmpty() && deque.peek()<=i-k){
deque.poll();
}
//2. 维护单调递减,新加入的要小于队列尾部，若新加入的大于队列尾部则弹出队列尾部！直到新加入的小于队列尾部为止！ ※※※
while( !deque.isEmpty() && num[i]>num[deque.peekLast()] ){
deque.pollLast(); // 弹出last直到新进来的都小于last
}
//3. 新元素的索引的入队列
deque.add(i); //存的是索引！
//存入窗口内最大值，由于队列是是单调递减的，即添加每一轮中队列中头部到list中即可
if(i>=k-1){ // 达到窗口宽度开始将队列头节点存入list
list.add(num[deque.peek()]); // 此处不能用poll !
}
}
return list;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89335.html
