📗difficulty： Medium
🎯Tags：
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
样例 1 ：
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
提示：
- 你可以假设
k总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
注意：本题与主站 239 题相同：https://leetcode-cn.com/problems/sliding-window-maximum/
以下题解来自于 leetcode-cn 用户 Krahets 的题解，感谢他的持续精彩分析。
一个大小为 K 的滑动窗口，向右滑动，前面的元素滑出，后面的元素滑入。双端队列的特征已经出来了。
本题需要求解的是窗口中的最大值，如果是对每个窗口求一次最大值，在没有特殊处理队列的情况下，整个复杂度会达到 O(n * K) 级别，如果能够在 O(1) 内完成获取最大值的工作，那么可以将复杂度下降到 O(n) 。
如果队列是“单调的”,只要保证队列头部 （or 尾部的值）为最大值，取出改元素即可。
有点类似与 剑指 Offer 30. 包含min函数的栈 ，需要对当前元素是否在队列中进行一个判断，如果改元素以及被滑出 滑动窗口了，相应地要从单调队列 中出队。
可以有 2 个循环，分为 滑动窗口形成前，和滑动窗口形成后。当一个滑动窗口形成了，此时，就产生了第一个需要加入最终 res[] 数组的元素，其位置在 deque.peekFirst()。
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) {
return new int[0];
}
int[] maxInWindows = new int[nums.length - k + 1];
// slideWindow 存储的是 非严格递减 的序列
Deque<Integer> slideWindow = new LinkedList<>();
// 初步建立滑动窗口
for (int i = 0; i < k; i++) {
// slideWindow 不为空 且 窗口最右边的数字 nums[i] 比它前面的数字都要大的话，就依次从队尾删除元素
// 保证了队列的头部元素最大
while (!slideWindow.isEmpty() && nums[i] > slideWindow.peekLast()) {
slideWindow.pollLast();
}
// 将 nums[i] 存入队列中
// 此时，队列 slideWindow 中元素是非严格递减的
// 队列头部元素值最大
slideWindow.offerLast(nums[i]);
}
// 大小为 k 的滑动窗口建立完成，继续处理
// 窗口的最大值存入最终的数组
maxInWindows[0] = slideWindow.peekFirst();
for (int i = k; i < nums.length; i++) {
// 如果队列头部的数字已经从其中滑出，那么滑出的数字也需要从队列的头部删除
// 例如 nums.length = 8,k = 3 的情况。for 循环第一轮，如果当前最大值为 nums[0] 需要删除它，因为已经滑过去了
if (!slideWindow.isEmpty() && slideWindow.peekFirst() == nums[i - k]) {
slideWindow.pollFirst();
}
// 这里的判断是严格大于，如果不是严格判断，会造成数据误删除
// 因为上面对元素是否出队进行了判断
while (!slideWindow.isEmpty() && nums[i] > slideWindow.peekLast()) {
slideWindow.pollLast();
}
slideWindow.offerLast(nums[i]);
maxInWindows[i - k + 1] = slideWindow.peekFirst();
}
return maxInWindows;
}- 时间复杂度：
O(n)。nums数组每个元素访问一次。 - 空间复杂度：
O(k)。不考虑最终返回数组需要的空间。存储滑动数组最大需要O(k)级别的空间。