文档教程后端【免费下载链接】interview-gogolang面试题集合https://interview.disign.me/项目地址https://gitcode.com/gh_mirrors/in/interview-go点击查看免费下载本文以 interview-go 仓库中algorithm/docs/sliding-window-maximum.md文档为核心完整解析「滑动窗口最大值」这道经典算法题先给出可直接运行的暴力解法再深入讲解时间复杂度为 O(n) 的双端队列单调队列解法并对照仓库源码 algorithm/sliding-window-maximum.go 验证两种实现的边界处理与测试入口。读完本文你将掌握滑动窗口类问题的通用分析路径以及用 Go 切片模拟双端队列写出线性复杂度的面试满分代码。01、题目描述与示例LeetCode 第 239 题滑动窗口最大值给定一个数组nums有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。请返回滑动窗口中的最大值所构成的数组。示例输入nums [1,3,-1,-3,5,3,6,7]k 3输出[3,3,5,5,6,7]窗口移动过程如下表滑动窗口的位置最大值[1 3 -1] -3 5 3 6 731 [3 -1 -3] 5 3 6 731 3 [-1 -3 5] 3 6 751 3 -1 [-3 5 3] 6 751 3 -1 -3 [5 3 6] 761 3 -1 -3 5 [3 6 7]7窗口每向右移动一位左侧出一个元素、右侧进一个元素因此共有L - k 1个窗口其中L len(nums)。本题对题目本身没有太多需要额外说明的难点在于如何高效地求出每个窗口的最大值。02、思路一暴力遍历求解最容易想到的思路是遍历所有滑动窗口对每个窗口内的k个元素求最大值。假设nums [1,3,-1,-3,5,3,6,7]k 3窗口数为 6外层循环定位每个窗口的起始下标index内层循环扫描窗口内k个元素找出最大值func maxSlidingWindow(nums []int, k int) []int { l1 : len(nums) ret : make([]int, 0) if l1 0 || k 0 { return ret } index : 0 for index l1 { m : nums[index] if index l1-k { break } for j : index 1; j indexk; j { if m nums[j] { m nums[j] } } ret append(ret, m) index } return ret }复杂度分析外层循环执行L - k 1次内层循环每次扫描k个元素总时间复杂度为O((L - k 1) × k) ≈ O(L×k)当k接近L/2时退化为 O(L²) 量级空间复杂度为O(1)不计结果数组仅使用常数个额外变量。暴力解法的优点是实现简单、易于理解适合在面试中先给出作为保底方案缺点是在大规模数据下性能不足无法通过 LeetCode 的大数据量用例。03、思路二双端队列单调队列线性解法暴力解法的主要矛盾在于窗口每滑动一次都需要重新扫描k个元素。如果能复用上一次窗口的最大值信息就能把单次求最大值的时间从 O(k) 降到均摊 O(1)。本题比较经典的解法有队列、DP、堆等多种方式所有思路的主要源头都是在窗口滑动的过程中如何更快地完成查找最大值的过程。而最典型的解法是使用双端队列Deque。3.1 什么是双端队列双端队列是一种同时具有队列和栈性质的数据结构队列中的元素可以从两端弹出或者插入。我们可以利用双端队列来实现一个窗口目的是让该窗口可以做到张弛有度——也就是队列长度动态变化。其实用游标或者其他解法的目的都是一样的就是去维护一个可变长的窗口并在窗口内部动态维护最大值信息。3.2 核心思路队头维护当前窗口最大值算法的核心可以概括为三步维护单调性遍历数组时若当前元素比队尾元素大就将队尾元素祭天出队直到队尾元素不小于当前元素再将当前元素入队。这样队内元素自队头到队尾严格递减队头永远是当前窗口的最大值淘汰过期元素当i k时下标i-k的元素已经滑出窗口若它恰好是队头元素则将其从队头出队收集结果当i k-1时窗口已满队头元素即当前窗口的最大值写入结果数组。整体图解如下假设nums [1,3,-1,-3,5,3,6,7]k 33.3 Go 实现用切片模拟双端队列Go 标准库没有内置双端队列但直接用切片即可模拟队尾操作对应append与queue[:len(queue)-1]队头操作对应queue[1:]。func maxSlidingWindow2(nums []int, k int) []int { ret : make([]int, 0) if len(nums) 0 { return ret } var queue []int for i : range nums { for i 0 (len(queue) 0) nums[i] queue[len(queue)-1] { // 将比当前元素小的元素祭天从队尾出队 queue queue[:len(queue)-1] } // 将当前元素放入 queue 中 queue append(queue, nums[i]) if i k nums[i-k] queue[0] { // 维护队列保证其头元素为当前窗口最大值 queue queue[1:] } if i k-1 { // 放入结果数组 ret append(ret, queue[0]) } } return ret }逐行拆解queue中存放的是元素值且自队头到队尾严格递减因此queue[0]恒为当前窗口的最大值第 6 行的出队循环保证新元素入队后队列仍然单调递减——任何一个比新元素小的旧元素都不可能再成为后续窗口的最大值因为新元素下标更靠后、生命周期更长所以可以安全删除第 10 行nums[i-k] queue[0]当队头元素恰好是滑出窗口的那个值时说明它已经过期需要从队头弹出。这里用值相等判断是安全的因为队内所有值互不重复地保留了单调序列中的关键值第 13 行i k-1时窗口恰好完全进入数组此后每个位置都对应一个完整窗口直接取队头入结果数组。复杂度分析每个元素最多入队一次、出队一次均摊到每次操作是 O(1)整体时间复杂度为O(n)队列最多容纳k个元素空间复杂度为O(k)不计结果数组。04、两种解法对比与源码验证仓库源码 algorithm/sliding-window-maximum.go 同时收录了上述两种实现并通过main函数直接验证func main() { arr : []int{1, 3} fmt.Println(arr[0:1]) nums : []int{1, 3, -1, -3, 5, 3, 6, 7} k : 3 ret : maxSlidingWindow2(nums, k) fmt.Println(ret) }对照源码可以看到两个值得注意的实现细节暴力版补全了边界检查maxSlidingWindow在文档代码基础上增加了if l1 0 || k 0 { return ret }避免空数组或k0时产生越界或死循环这是面试中容易被忽略的健壮性细节单调队列版直接返回空切片maxSlidingWindow2对len(nums) 0提前返回逻辑更简洁。对比维度暴力遍历maxSlidingWindow双端队列maxSlidingWindow2时间复杂度O(n×k)O(n)空间复杂度O(1)O(k)实现难度低易于讲解中需理解单调性维护适用场景小数据量、快速交付大数据量、面试最优解你可以直接在仓库中运行go run algorithm/sliding-window-maximum.go验证输出是否为[3 3 5 5 6 7]。05、延伸思考其他可行解法除了双端队列本题还有两条经典路径理解它们有助于面试时展示知识广度优先队列堆维护一个大顶堆堆顶即窗口最大值窗口滑动时把出窗口的元素标记为惰性删除推迟到它成为堆顶时再弹出。时间复杂度同为 O(n log k)代码相对复杂动态规划 / 分段预处理将数组按k分段分别从左向右、从右向左预处理块内前缀/后缀最大值再按窗口跨越的块组合出每个窗口的最大值时间复杂度 O(n)、空间复杂度 O(n)。06、小结滑动窗口最大值是一道高频面试题核心考点有三窗口数量公式L - k 1所有滑动窗口类问题的公共基础暴力解法兜底O(n×k) 的实现要能快速写出并准确说明复杂度单调队列优化用双端队列在 O(n) 时间内维护窗口内递减序列队头即最大值——这一思想同样适用于滑动窗口最小值滑动窗口中位数等变体题目。对 Go 开发者而言掌握用切片模拟双端队列的技巧还能顺带覆盖 Go 面试中常见的切片截取、扩容、复用等底层细节。建议对照仓库源码 algorithm/sliding-window-maximum.go 亲手运行一遍并尝试把数组元素下标而非元素值存入队列作为进阶练习验证对单调队列原理的理解。赞分享文档教程后端【免费下载链接】interview-gogolang面试题集合https://interview.disign.me/项目地址https://gitcode.com/gh_mirrors/in/interview-go点击查看免费下载相关推荐AlgoNote 算法通关LeetCode 239 滑动窗口最大值——优先队列与单调队列双解法剖析AlgoNote 算法通关LeetCode 239 滑动窗口最大值——优先队列与单调队列双解法剖析 导读 本篇基于「算法通关手册」AlgoNote 仓库的 0教程文档知识库滑动窗口最大值LeetCode 239单调队列题解从裁员比喻到三步套路附 codeforces-go 模板实现滑动窗口最大值LeetCode 239单调队列题解从裁员比喻到三步套路附 codeforces go 模板实现 单调队列Monotone Queue科学计算用 GetQzonehistory 快速完成QQ空间说说备份的完整指南用 GetQzonehistory 快速完成QQ空间说说备份的完整指南 GetQzonehistory 是一个免费的开源 Python 项目专门用来备份自己账网页爬虫数据分析上一篇ReactPy中的SSE客户端实现终极指南教你处理服务器发送事件下一篇tchMaterial-parser智能解析技术如何优化电子课本获取体验创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考