牛客网 面试笔试 TOP101 | LeetCode 239. 滑动窗口最大值
1. 题目
描述
给定一个长度为 n 的数组 nums 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。
例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
数据范围： 1 ≤size≤n≤10000，数组中每个元素的值满足 |val| ≤10000
要求：空间复杂度 O(n)，时间复杂度 O(n)
示例1
输入：
[2,3,4,2,6,2,5,1],3
返回值：
[4,4,6,6,6,5]
示例2
输入：
[9,10,9,-7,-3,8,2,-6],5
返回值：
[10,10,9,8]
示例3
输入：
[1,2,3,4],3
返回值：
[3,4]
2. 解题思路
本题可以通过双端队列完成，先来看一下什么是双端队列：
双端队列是一种允许在队列头部和尾部进行插入（enqueue）和删除（deque）操作的线性数据结构。它结合了队列（FIFO）和栈（LIFO）的特性，具有高度的灵活性。
核心特性
双向操作：
支持在队头（Front）和队尾（Rear）进行插入（
push_front,push_back）和删除（pop_front,pop_back）。灵活性：
既可以实现普通队列的先进先出（FIFO），也可以实现栈的后进先出（LIFO）。
时间复杂度：
大多数实现（如链表或动态数组）的插入和删除操作时间复杂度为 O(1)。
与普通队列的区别
操作 普通队列 双端队列 插入 只能在队尾插入 队头和队尾均可插入 删除 只能在队头删除 队头和队尾均可删除 双端队列（Deque，全称 Double-ended Queue）是一种允许在队列的头部和尾部同时进行插入和删除操作的数据结构。它结合了队列（FIFO）和栈（LIFO）的特性，是许多算法和场景中的高效工具。
常见应用场景
滑动窗口算法：如求最大值/最小值的窗口（方便两端操作）。
回文检测：从两端向中间逐对比较字符。
撤销操作：保存操作历史，支持前进/后退（类似浏览器历史）。
多线程工作窃取：如 Java 的
ForkJoinPool使用双端队列平衡任务分配。
如果文字描述的不太清楚，你可以参考视频的详细讲解。
-
Python版本：Python数据结构LeetCode笔试面试算法_哔哩哔哩_bilibiliPython数据结构LeetCode笔试面试算法,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕
https://www.bilibili.com/cheese/play/ep1372595 -
Java版本：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ep1367851 -
Golang版本：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ep1364849
3. 编码实现
核心代码如下：
/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param num int整型一维数组* @param size int整型* @return int整型一维数组*/
func maxInWindows(num []int, size int) []int {// write code hereres := make([]int, 0)//窗口大于数组长度的时候，返回空if size == 0 || size > len(num) {return res}//1. 定义一个双端队列（队列中存储的是数组元素的下标）dq := newDeque()//2. 先遍历第一个窗口for i := 0; i < size; i++ {//队列中只保留单调递减的序列（将所有比 当前值 小的元素全部弹出）；队列中存储的是数组元素的下标，下标对应的数组元素为单调递减for !dq.isEmpty() && (num[dq.back()] < num[i]) {dq.popBack()}//当前值入队列（加入队列的值为：数组下标）dq.pushBack(i)}//3. 遍历后续数组元素for i := size; i < len(num); i++ {//3.1 取窗口内的最大值index := dq.front()res = append(res, num[index])//3.2 判断队列的头部的下标是否过期if !dq.isEmpty() && (i-dq.front()+1) > size {dq.popFront() //头部出队列}//3.3 队列中只保留单调递减的序列（将所有比 当前值 小的元素全部弹出）for !dq.isEmpty() && num[dq.back()] < num[i] {dq.popBack() //弹出较小的值，尾部出队列}//3.4 当前值入队列（加入队列的值为：数组下标）dq.pushBack(i)}//4. 最后还剩一组res = append(res, num[dq.front()])return res}具体完整代码你可以参考下面视频的详细讲解。
-
Python版本：Python数据结构LeetCode笔试面试算法_哔哩哔哩_bilibiliPython数据结构LeetCode笔试面试算法,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕
https://www.bilibili.com/cheese/play/ep1372595 -
Java版本：LeetCode数据结构笔试面试算法-Java版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Java版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕
https://www.bilibili.com/cheese/play/ep1367851 -
Golang版本：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ep1364849
4.小结
通过双端队列来求解滑动窗口的最大值，具体步骤为：
-
定义一个双端队列，队列中存储数组元素的下标；
-
队列中下标对应的元素为单调递减；
-
依次将数组中的下标入队列。在此过程除了满足条件1与2外，还需要满足：队列中头部下标不能过期，即 i<（front(dq)+size）,其中i为数组的下标，dp为双向队列，size为窗口大小。
《数据结构与算法》深度精讲课程正式上线啦！7 大核心算法模块全解析：
✅ 链表
✅ 二叉树
✅ 二分查找、排序
✅ 堆、栈、队列
✅ 回溯算法
✅ 哈希算法
✅ 动态规划
无论你是备战笔试面试、提升代码效率，还是突破技术瓶颈，这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡，与千名开发者共同进阶！
-
Python编码实现：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ss897667807 -
Java编码实现：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ss161443488 -
Golang编码实现：LeetCode数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕
https://www.bilibili.com/cheese/play/ss63997
对于数据结构与算法，我们总结了一套【可视化+图解】方法，依据此方法来解决相关问题，算法变得易于理解，写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。
今日佳句：此情可待成追忆？只是当时已惘然。
