滑动窗口的最大值
题目描述
示例
代码
代码1 暴力解法，挨个找滑动窗口中的最大值，输出结果
这种方法会有很多重复的比较，比位于两个相邻窗口中的数，会比较多次。
比如示例1中的，滑动窗口1：2 3 4，找最大值的时候， 3 4 已经比较一遍了
滑动窗口2：3 4 2，找最大值时，3 4又比较了一次。
所以暴力的解法并不是最优的，会多出很多重复的操作。
js
/*
1. 两个指针，i j 控制滑动窗口
2. 定义一个方法比较当前滑动窗口的值，找出最大值
3. 将最大值push到一个数组中
4. 当j的索引大于 num.length - 1 时，结束比较
5. 返回结果
*/
function maxInWindows(num, size)
{
if(size === 0 || size > num.length) return []
let result = [] // 保存输出的结果
// 维护的滑动窗口的两个指针
let i = 0
let j = i + size - 1
// 当窗口越界了，结束循环
while(j < num.length){
result.push( findMax( num, i, j ) ) // 找到当前滑动窗口的最大值，存到结果数组中
i++
j++
}
return result // 返回结果
// 找到当前滑动窗口最大值
function findMax( arr, begin, end ){
let max = 0
while( begin <= end ){
if(arr[begin] > max){
max = arr[begin]
}
begin++
}
return max
}
}时间复杂度O(n*k)：k为滑动窗口长度，每个窗口都需要找最大值，比较k次
空间复杂度O(1)
代码2 使用双端单调队列，记录每次的结果
- 遍历数组的每一个元素，
- 如果容器为空，则直接将当前元素加入到容器中。
- 如果容器不为空，则让当前元素和容器的最后一个元素比较，如果大于，则将容器的最后一个元素删除，然后继续讲当前元素和容器的最后一个元素比较
- 如果当前元素小于容器的最后一个元素，则直接将当前元素加入到容器的末尾
- 如果容器头部的元素已经不属于当前窗口的边界，则应该将头部元素删除
js
/*
使用双端单调队列
*/
function maxInWindows(num, size)
{
if(num.length ===0 || size > num.length || size == 0) return []
let result = [] // 存放结果
let q = [] // 定义一个队列
for(let i = 0; i< num.length; i++){
// 单调队列是递减的，头部永远保存当前滑动窗口的最大值
// 队列中存的是数组的索引，且要保证值是单调递减的
// 如果下一个值比当前值大，就把当前这个值删除掉
// 如果下一个值比当前值小，就把下一个值入队
while(q.length > 0 && num[ q[q.length-1] ] < num[i] ){
q.pop()
}
q.push(i) // 队列存的是索引
// 判断队列头部这个值是否过期
if( i-size >= q[0] ){ // 队列中存的是数组值的索引
// 表示已过期，把头部这个过期值删除掉
q.shift()
}
// 如果索引开始大于 滑动窗口的时候，可以开始存结果了
if(i >= size-1){
result.push( num[q[0]] )
}
}
return result
}时间复杂度O(n)
空间复杂度O(1)