题目
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
分析
这道题先用暴力求解演练一遍对解题是有帮助的，因为它并没其它奇思妙想，都是在暴力法上加速。
先过一遍暴力法的过程：窗口每向前滑动一格，剔除最左边元素后再求窗口内最大值，过程非常简单。
暴力法时间复杂度为O(k*n),原因在于在每个窗口内找出最大值，每次都需要比较K次，加速的目标就在这。
问题核心其实就是求出动态数组最大值，如果将数组变成一个单向队列，可以将比较次数从K次减为1次，但维护有序数组每次插入新元素还是需要可能比较K次，这个时候可以通过删除可以被淘汰的数据来减少比较。
使用双端队列更方便淘汰元素，队列内维护不多于窗口大小的元素，队首是最大元素，并且始终保持从大到小的顺序，为了达到这个目的，每次加元素入队尾前,将比它小的元素淘汰，这样队列只保存了有意义数据,同时只保存元素下标会更方便淘汰窗口外的数据.
代码
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deque = new LinkedList<Integer>();
int size = nums.length -k >= 0 ? nums.length - k + 1 : 1;
int[] result = new int[size];
for(int i=0;i<nums.length;i++){
while(deque.size()>0 && nums[deque.peekLast()] <= nums[i]){
deque.pollLast();
}
deque.addLast(i);
if(i - deque.peekFirst() >= k){
deque.pollFirst();
}
int index = i-k+1>=0? i-k+1:0;
result[index] = nums[deque.peekFirst()];
}
return result;
}
}结果
关注个人微信公众号：肌肉码农，回复“好友”讨论问题。
?