算法:滑动窗口最大值(滑动窗口算法原理)
给你一个整数数组nums
,有一个大小为k
的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的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复制代码
示例 2:
输入: nums = [1], k = 1 输出: [1]复制代码
示例 3:
输入: nums = [1,-1], k = 1 输出: [1,-1]复制代码
示例 4:
输入: nums = [9,11], k = 2 输出: [11]复制代码
示例 5:
输入: nums = [4,-2], k = 2 输出: [4]复制代码
提示:
1 <= nums.length <= 10510^5105
-10410^4104 <= nums[i] <= 10410^4104
1 <= k <= nums.length
以数组nums[1,3,-1,-3,5,3,6,7]
为例,假如滑动长度k为3,从前往后滑动,找出每一次滑动窗口内的最大值,并存储到result数组中,分析如下:
第一次,窗口为
[1,3,-1]
,最大值为3,result为[3]第二次,窗口为
[3,-1,-3]
,最大值为3,result为[3, 3]第三次,窗口为
[-1,-3,5]
,最大值为5,result为[3, 3, 5]第四次,窗口为
[-3,5,3]
,最大值为5,result为[3, 3, 5, 5]第五次,窗口为
[5,3,6]
,最大值为6,result为[3, 3, 5, 5, 6]第六次,窗口为
[3,6,7]
,最大值为7,result为[3, 3, 5, 5, 6, 7]
每次滑动需要从窗口的数组中找出最大值,一般都能想到暴力解法,采用双层遍历,外层遍历整个nums数组,内层遍历滑动窗口数组,代码如下:
/** * 暴力解法,双层遍历,外层遍历len - k + 1次,内层遍历k次,每次取出最大值 * 时间复杂度O(N²) * @param {数组} nums * @param {滑窗长度} k * @returns 滑动窗口最大值 */ function maxSlidingWindow(nums, k) { const result = [] if (k > nums.length) { throw new Error('k不能大于nums的长度') } const slidLen = nums.length - k + 1 let maxIndex = -1 for (let i = 0; i < slidLen; i++) { // maxIndex存储了上一次窗口的最大值索引,当前遍历判断maxIndex是否包含在窗口内 // 如果包含,则将窗口最后一个值与maxIndex对应的元素比较 if (maxIndex >= i) { if (nums[i + k - 1] > nums[maxIndex]) { maxIndex = i + k - 1 result[i] = nums[maxIndex] continue } } let max = -Infinity for (let j = i; j < i + k; j++) { if (max <= nums[j]) { maxIndex = j max = nums[j] } } result[i] = max } return result };复制代码
以上代码相对于直接的暴力解法做了一点优化,在遍历窗口时,存储了当前窗口最大值的索引maxIndex,在下一次遍历时先判断maxIndex是否包含在窗口内,是则直接和最后一个值nums[i + k - 1]
比较大小即可。
比较理想的情况是,数组为递增,例如[1, 3, 5, 6, 6, 7],这样maxIndex都将包含在当前窗口内,不会再完全遍历整个窗口。但最坏的情况,例如数组[7, 6, 6, 5, 3, 1],数组递降,maxIndex始终不包含在当前窗口,需要完全遍历第二层滑动窗口。
暴力解法的时间复杂度为O(N2N^2N2)。
对于以上的暴力解法,考虑如何优化,要解决的问题是如何减少单次滑动窗口的遍历次数,如果能将时间复杂度降为O(N),是最理想的情况。
暴力解法只存储了上一次窗口的最大值,没有考虑倒序的情况,如果能用一个数组统一维护每一次滑动窗口的元素,并且按倒序排列,那么下一次遍历就可以不用再遍历整个滑动窗口了。例如第一个滑动窗口数组按倒序排列[5,3,1]
,由于5是在最后一位并且是最大的,所以只保留[5]即可。
还是以数组nums[1,3,-1,-3,5,3,6,7]
,滑动窗口k=3为例,排序数组为dequeue,分析过程:
第一次,窗口为[1,3,-1], dequeue为[3,-1], result为[3]
第二次,窗口为[3,-1,-3], dequeue为[3, -1, 3],result为[3, 3]
第三次,窗口为[-1,-3,5], 3不在窗口内,dequeue变为[5],result为[3, 3, 5]
第四次,窗口为[-3,5,3], dequeue为[5, 3],result为[3, 3, 5, 5]
第五次,窗口为[5,3,6], dequeue变为[6], result为[3, 3, 5, 5, 6]
第六次,窗口为[3,6,7], dequeue变为[7], result为[3, 3, 5, 5, 6, 7]
dequeue为双向队列,新的值从队尾插入,只有队尾的元素大于新值才允许插入,否则移除队尾元素直到满足条件。另外一点,队首元素始终为最大值,并且要属于滑动窗口,否则需要从队列中移除掉。
/** * 将已经遍历过的元素用双向队列维护起来,并且双向队列中存储的元素满足倒序排序。 * 双向队列要求,所有元素从队尾入队,如果队尾元素小于要推入的元素,则移除队尾元素,直到满足要推入的元素小于队尾元素 * 双向队列存储的元素,必须是在[l, r]区间的,否则从队首移除。 * @param {}} nums * @param {*} k * @returns */ function maxSlidingWindow(nums, k) { const result = [] if (k > nums.length) { throw new Error('k不能大于nums的长度') } let dequeue = [], left = right = 0 for (let i = 0; i < nums.length; i++) { // 如果当前元素大于队列尾部元素,删除尾部元素 while (dequeue.length && nums[dequeue[dequeue.length - 1]] < nums[i]) { dequeue.pop() } dequeue.push(i) // 移除队列中索引小于left的 while(dequeue.length && dequeue[0] < left) { dequeue.shift() } // 长度满足滑动窗口 if (right - left + 1 === k) { result.push(nums[dequeue[0]]) left++ } right++ } return result };复制代码
在维护dequeue时,为了对比滑动滑动窗口范围,直接存储对应元素的索引,例如判断队首最大值的索引是否包含在窗口内,可直接判断dequeue[0] < left。
通过双线队列来维护滑动窗口,时间复杂度满足O(N2N^2N2)。
要从滑动窗口队列中选出最大值,还可以考虑使用最大堆,将滑动窗口队列通过最大堆维护,这样可以直接找到最大值。最大堆通过二叉树实现,根节点始终保存队列的最大值,每个节点的特点是,其元素值大于两个子节点。
假如MaxHeap为最大堆类型,其实现文章最后会附上源代码,通过最大堆实现查询滑动窗口最大值代码如下:
/** * 使用最大堆实现,将最大窗口内的元素使用最大堆管理,每次取出的元素为堆中的最大元素 * @param {}} nums * @param {*} k * @returns */ function maxSlidingWindow(nums, k) { const result = [] if (k > nums.length) { throw new Error('k不能大于nums的长度') } //MaxHeap为最大堆对象,默认为空 let left = 0, right = 0, maxHeap = new MaxHeap([]) for (let i = 0; i < nums.length; i++) { maxHeap.insert(nums[i]) if (right - left + 1 === k) { // 当达到滑动窗口长度,将最大堆的根节点data[0]保存到result result.push(maxHeap.data[0]) // 将滑动窗口最左端的元素从最大堆中移除 maxHeap.deleteV(nums[left]) left++ } right++ } return result }复制代码
当left、right之间长度达到k,每次遍历直接将最大堆根元素保存到结果队列中,MaxHeap包含deleteV函数,用于从最大堆移除某个元素。
由于滑动一次窗口,最大堆都将重新排列一次,所以其时间复杂度和暴力解法一样,都为O(N2N^2N2)。
最后附上最大堆的JS代码实现:
function swap(data, i, j) { const temp = data[i] data[i] = data[j] data[j] = temp } function left(i) { return 2 * i + 1 } function right(i) { return 2 * i + 2 } /** * 最大堆 * 数据存储在数组中,index为数组下标 * 二叉树左侧节点用index * 2 + 1表示,右侧节点用idnex * 2 + 2表示 * 二叉树叶子节点表达式 序号 >= floor(N / 2), N为数组长度 */ class MaxHeap { data = [] size = 0 constructor(data) { this.data = data || [] this.size = this.data.length } /** * 调整节点,使当前节点满足最大堆 * @param {*} i */ adjust(i) { let maxIndex = i, l = left(i), r = right(i) if (l < this.size && this.data[l] > this.data[maxIndex]) { maxIndex = l } if (r < this.size && this.data[r] > this.data[maxIndex]) { maxIndex = r } // 如果max为元素,则满足最大堆,不需要重新处理 if (maxIndex === i) { return } swap(this.data, i, maxIndex) this.adjust(maxIndex) } /** * 插入新元素 * @param {新元素} value */ insert(value) { this.data[this.size] = value this.size++ if (this.isHeap()) { return } this.build() } /** * 删除元素 * @param {索引}} index */ delete(index) { // 从data中删除元素,重新构建 this.data.splice(index, 1) this.size-- this.build() } deleteV(value) { const index = this.data.indexOf(value) if (index > -1) { this.delete(index) } } /** * 构建最大堆 * 从 N/2 - 1开始遍历,调整每个节点,使其满足最大堆 */ build() { for (let i = Math.floor(this.size / 2) - 1; i >= 0; i--) { this.adjust(i) } } /** * 判断是否为堆 */ isHeap() { for (let i = Math.floor(this.size / 2) - 1; i >= 0; i--) { const left = i * 2 + 1, right = i * 2 + 2 if (this.data[i] < this.data[left] || this.data[i] < this.data[right]) { return false } } return true } /** * 生成升序排序数组 * 最大堆第一个元素为最大值,将其和最后一个元素交换,然后设置堆的size减1 */ sort() { while (this.size) { swap(this.data, 0, this.size - 1) this.size-- this.adjust(0) } } }复制代码
如果大家有其他问题可直接留言,一起探讨!最近我会持续更新Vue源码介绍、前端算法系列,感兴趣的可以持续关注。
作者:前端下饭菜
链接:https://juejin.cn/post/7051215593839525902