LeetCode上滑动窗口最大值，第一次做hard难度，记录下解题思路
一开始是想直接暴力循环，比如传入nums = [1,3,-1,-3,5,3,6,7], k = 3
从0位循环到nums.length - k位置，然后每次都取k范围的区间，在这个区间中循环求得最大的数，把这个数推入结果数组即可，那么就会得到下面代码
var maxSlidingWindow = function(nums, k) {
// nums为给定数组，k为窗口大小
if (k===1) return nums
if (nums.length===0) return []
// 返回结果数组
let res = []
for(let i = 0; i<=nums.length - k; i++) {
// 从第0位开始循环取k大小的区间，并且取出这个区间中的最大值
// Number.MIN_SAFE_INTEGER 代表最小安全值
let num = Number.MIN_SAFE_INTEGER
for(let j = i; j< i + k; j++) {
// 对每个区间循环
num = Math.max(num,nums[j])
}
res.push(num)
}
return res
};
其实上面的代码对于数组长度不大的数据还是可以处理的，但是进行最后提交的时候就会出现超时，面对数组很大的情况下，多重循环会让程序执行时间太长。
会使用到一个双端队列的方法来解决问题
Deque 的含义是 “double ended queue”，即双端队列，它具有队列和栈的性质的数据结构。顾名思义，它是一种前端与后端都支持插入和删除操作的队列。
图片来源，从这个图片上面就能很好的理解双端队列解决这个问题的原理：
- 保证
deque数组中队首都是当前数组中的最大值，deque保存的都是index - 每次遍历的时候，都会对比当前deque的队尾和目前值的大小关系，如果比当前数小，就要删除队尾，同时要一直循环直到，队尾的数字比当前数大
- 之后把当前数的index放入deque中
- 检查队头元素，如果队头元素的index已经超出了窗口范围，就要删除队头，比如目前队头是2，k=3，i=3，那么窗口就是index为[3,4,5]的数，此时队头是2，那么就要删除队头，保证deque的数据都在窗口内
- 当循环到了窗口所需次数之后，例如窗口为3，那么i就要循环0/1/2，3次来让窗口形成，此时deque队列的队首就是每次窗口中的最大数了。
var maxSlidingWindow = function(nums, k) {
// 缓存数组的长度
const len = nums.length;
const res = [];
const deque = [];
for (let i = 0; i < len; i++) {
// 队尾元素小于当前元素
while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
// 当deque数组存在且存在nums[deque[deque.length - 1]] 会输出当前deque数组的队尾数
// 如果队尾数< nums[i]，则删除队尾数
deque.pop()
}
// 当deque不存在的时候或者nums[i]小于队尾就会保存当前数，是保存当前数的index
deque.push(i)
// 当队头元素的索引已经被排除在滑动窗口之外时
while (deque.length && deque[0] <= i - k) {
// 队头元素出对
deque.shift()
}
// 从第k-1次循环开始输出结果
if (i >= k - 1) {
res.push(nums[deque[0]])
}
}
return res
}
假设传入nums = [1,3,-1,-3,5], k = 3
第一轮： i=0 此时deque.length为0不行进行两个while循环，只会push，此时deque=[0]
第二轮： i=1 此时deque.length = 1
且nums[deque[deque.length - 1]] = nums[deque[0]]=nums[0]=1
1<nums[1]= 1<3成立，删除队尾
此时deque=[]，deque.length = 0，不继续循环
然后将i=1放入数组，此时数组deque=[1]，
deque.length && deque[0] <= i - k = 1 < -2 不成立，
i >= k - 1 = 1>2 不成立
第三轮 i=2，此时deque.length = 1
nums[deque[deque.length - 1]] = nums[deque[0]]=nums[0]=1
1<nums[2]= 1< -1，不成立
那deque.push(i)保存当前index，deque=[1,2]
此时deque.length = 2
deque.length && deque[0] <= i - k = 1 < 1 不成立
i >= k - 1 = 2>=2，成立
将nums[deque[0]]，放入结果数组，res=[3]
第四轮 i=3，此时deque.length = 2
nums[deque[deque.length - 1]] = nums[deque[1]]=nums[2]=-1
-1<nums[3]= -1< -3，不成立
那deque.push(i)保存当前index，deque=[1,2,3]，那么此时deque.length = 3
deque.length && deque[0] <= i - k = 1 < 0 不成立
i >= k - 1 = 2>=2，成立，将nums[deque[0]]，放入结果数组，res=[3,3]
第五轮 i=4，此时deque.length = 3
nums[deque[deque.length - 1]] = nums[deque[2]]=nums[3]=-3
-3<nums[4]= -3< 5，成立，删除队尾
此时deque=[1,2]，deque.length = 2
nums[deque[deque.length - 1]] = nums[deque[1]]=nums[2]=-1
-1<nums[4]= -1< 5，成立，删除队尾
此时deque=[1]，deque.length = 1
nums[deque[deque.length - 1]] = nums[deque[0]]=nums[1]=3
3<nums[4]= 3< 5，成立，删除队尾
此时deque=[]，deque.length = 0，不继续循环
上面的循环清空了整个数组，然后才推入当前数，保证deque的队首一定是最大的那个数
此时deque.push(i)保存当前index，deque=[4]，那么此时deque.length = 1
deque.length && deque[0] <= i - k = 4 < 1 不成立
i >= k - 1 = 2>=2，成立，将nums[deque[0]]，放入结果数组，res=[3,3,5]
此时整个for循环结束，返回res
