滑动窗口最大值：单调队列原理与代码实现全解析

滑动窗口最大值这题很多人第一次碰到是在LeetCode 239上看起来就是个“滑动窗口里找最大”的数组题实际上背后藏着单调队列这种非常经典的数据结构思想。面试里它几乎是必考题而且面试官往往会追问各种变形为什么暴力解过不了堆为什么不是最优单调队列到底在维护什么如果只是背过答案很容易在追问环节露馅。这篇文章我把这道题从原理到代码彻底拆开从暴力解法的缺陷讲起到双端队列维护单调性、再到各种边界坑点最后把滑动窗口最小值、中位数、硬件滤波这类延伸场景一并串起来希望读完你不仅能AC这道题还能理解它背后的通用套路。1. 题目拆解先看清楚问题再动手1.1 题目到底在问什么给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到最右侧。你只可以看到在滑动窗口内的 k 个数字滑动窗口每次只向右移动一位要求返回滑动窗口中最大值组成的数组。举个例子nums [1,3,-1,-3,5,3,6,7]k 3。窗口从最左边开始第一次窗口覆盖 [1,3,-1]最大值是3右移一位后窗口覆盖 [3,-1,-3]最大值还是3再右移覆盖 [-1,-3,5]最大值变成了5……最后一共输出 n - k 1 个最大值也就是 8 - 3 1 6 个结果[3,3,5,5,6,7]。这个题表面上是“求数组区间最大值”但它有个特殊约束窗口是固定长度的而且每次只移动一步。这个约束决定了我们不能简单地把每个窗口当作独立区间处理因为相邻窗口之间有大量重叠——如果能利用这种重叠关系就能避免重复计算。我见过不少初学者第一反应是排序把每个窗口里的k个数排个序取最大。这个思路在数据量小的时候没错但一旦k接近n比如数组长度10万、窗口大小5万排序的总代价会高到无法接受。问题的关键在于滑动窗口是一种流式过程我们要的不是单次查询而是连续、实时地维护一个动态集合的极值。1.2 暴力解法为什么不行最直观的解法就是枚举所有窗口对每个窗口从头到尾扫一遍找最大值。外层循环有 n - k 1 个窗口每个窗口内部扫描 k 个元素总时间复杂度是 O(nk)。当 n 和 k 都取到 10^5 级别时n乘以k就是10^10次操作在常规OJ上基本是超时级别的。就算 k 比较小这个写法也谈不上优雅。更关键的是暴力解法完全没有利用窗口移动的重叠信息——窗口向右移一格只是丢掉最左边一个元素、加入最右边一个新元素其余 k - 1 个元素根本没有任何变化但我们还是把整个窗口重新扫了一遍这是在反复做无用功。还有一种常见思路是用大顶堆优先队列把当前窗口的元素全部塞进堆里堆顶就是最大值。窗口移动时删除离开的元素、添加新元素然后取堆顶。这个方向比暴力好不少时间复杂度是 O(n log k)。不过它可以继续优化因为堆的删除操作往往需要“延迟删除”而且堆里维护了所有窗口元素但我们真正需要的只是“当前窗口里的最大值”大量非最大元素其实根本没必要保留。如果面试时你回答“用优先队列”面试官大概率会追问一句“能不能做到O(n)” 这时候就是单调队列登场的时候了。1.3 窗口移动时发生了什么为了设计高效解法需要非常具体地描述窗口移动的每一步操作。假设窗口右边界已经到下标 i窗口覆盖范围是 [i - k 1, i]。窗口向右移动一位后右边界变成 i 1覆盖范围变成 [i - k 2, i 1]。对比移动前后的窗口只有一个元素离开下标 i - k 1和一个元素加入下标 i 1。所以理想情况下每次移动我们只需要处理“一个出队”和“一个入队”然后想办法快速知道新的最大值。问题转化成维护一个动态数据集合支持在集合头部删除一个元素、在集合尾部插入一个元素并且能快速返回集合中的最大值。数组的随机访问、链表的头尾插入删除都很快但“快速求最大值”这个需求需要额外设计。单调队列就是为这个场景量身定做的它本质上是一个双端队列但通过维护队列内元素的单调性让队首永远保存当前窗口的最大值。2. 单调队列这道题的标准答案2.1 为什么偏偏是双端队列双端队列Deque允许从队首和队尾两端进行插入和删除。滑动窗口移动时过期元素从窗口左端离开新元素从窗口右端进入天然对应了双端队列的头部删除和尾部插入。但仅仅支持两端的插入删除还不够我们还需要快速拿到最大值。如果队列元素是无序的找最大值还得遍历那就白折腾了。所以核心思路是让队列里的元素保持某种单调性——比如从队首到队尾单调递减。这样队首就是最大值每次取答案只要 O(1)。维持单调性的办法也很巧妙当新元素要入队时不断从队尾弹出所有比新元素小的元素以及后面会讨论的等于的情况直到队尾元素比新元素大或者队列为空然后把新元素从队尾入队。为什么可以放心弹出队尾那些较小的元素因为这些被弹出的元素下标都比新元素小它们是先来的而值又比新元素小或者相等。在滑动窗口的视角下新元素“又大又新”意味着只要新元素还在窗口里那些旧的小元素就永远不可能是窗口最大值。既然它们已经对答案没有贡献留着只会增加队列长度不如直接弹掉。这一手就是单调队列的精髓——用“下标更大、值也更大”的元素去淘汰不可能成为答案的“前辈”。2.2 队列里到底存下标还是存值很多第一次写单调队列的人会下意识把元素值本身存进队列这其实埋了个大坑当窗口移动、需要判断队首元素是否已经滑出窗口时光有值根本无法判断它是什么时候进来的也就无法判断它是否过期。正确的做法是队列里存数组下标比较大小的时候用 nums[下标] 去取值。这样做了两件事一是可以通过下标判断元素是否在窗口范围内二是取最大值答案时可以直接用 nums[队首下标]不需要额外存储。这里顺便说一下队列单调性的方向。我们要维护的是“最大值”所以队列里的元素值从队首到队尾应该是递减的队首最大。如果题目改成求滑动窗口最小值就把单调性反过来队列里元素值从队首到队尾递增队首最小。整个算法框架不变变的只是比较符号和弹出条件。2.3 完整手推一个例子用 nums [1,3,-1,-3,5,3,6,7] 和 k 3 来手动走一遍流程你会彻底理解每个步骤的意义。队列 q 初始为空。i 0nums[0] 1队列空直接把下标0入队。q [0]。i 1nums[1] 3队尾下标0对应的值是13 1所以弹出下标0然后把下标1入队。q [1]。i 2nums[2] -1队尾下标1对应的值是3-1 3不弹出直接把下标2入队。q [1, 2]。此时窗口 [0,2] 已经形成队首下标1对应的值是3记录结果 3。i 3nums[3] -3队尾下标2对应的值是-1-3 -1不弹出入队下标3。q [1, 2, 3]。先检查队首下标1是否过期窗口左边界是 i - k 1 1下标1没有过期队首值3记录结果3。i 4nums[4] 5队尾下标3对应的值是-35 -3弹出下标3队尾下标2对应的值是-15 -1弹出下标2队尾下标1对应的值是35 3弹出下标1队列空入队下标4。q [4]。窗口左边界是 2下标4自然没过期队首值5记录5。i 5nums[5] 3队尾下标4对应的值是53 5不弹出入队下标5。q [4, 5]。窗口左边界是3队首下标4没过期队首值5记录5。i 6nums[6] 6队尾下标5对应的值是36 3弹出下标5队尾下标4对应的值是56 5弹出下标4队列空入队下标6。q [6]。窗口左边界是4下标6没过期队首值6记录6。i 7nums[7] 7队尾下标6对应的值是67 6弹出下标6入队下标7。q [7]。队首值7记录7。最终结果 [3,3,5,5,6,7]和题目要求的输出完全一致。整个过程每个元素最多入队一次、出队一次均摊下来每次操作就是 O(1)总复杂度 O(n)。注意到这个过程中有一个重要细节比如 i3 的时候窗口其实已经包含了下标1、2、3三个元素队列里也是 [1,2,3]三个元素都在窗口内没有冗余。而 i4 的时候窗口是 [2,3,4]但队列里只剩 [4] 了因为下标2、3对应的 -1、-3 都被 5 淘汰掉了——它们确实不可能成为当前或未来窗口的最大值因为 5 比它们大而且比它们晚过期。2.4 为什么这道题不能用线段树、ST表这类RMQ结构看到这里可能有朋友会问区间最大值不是还可以用线段树、ST表、稀疏表之类的RMQ结构吗确实可以但它们在滑动窗口场景下都不是最优解。ST表可以做到 O(1) 查询任意区间最大值但预处理是 O(n log n) 的。滑动窗口是一个在线过程窗口每次移动都要查一次如果用 ST表总复杂度 O(n log n n)多了个 log 不太划算。线段树支持单点更新和区间查询也可以 O(log n) 地维护窗口但同样带 log。单调队列之所以是这道题的“标准答案”就是因为滑动窗口有一个其他场景没有的特性窗口左边界和右边界都在同方向单调移动。这个特性让我们可以只用一个双端队列在线性时间内完成全部任务。如果题目变成“数组不变、任意询问区间最大值”那才需要用 ST表或者线段树如果变成“数组动态修改、询问区间最大值”那线段树和树状数组这类结构才是合适的。不同的动态性对应不同的数据结构这是算法题里特别重要的一种思考方式。3. 三种主流语言实现与代码细节3.1 Java 版本基于 ArrayDequeclass Solution { public int[] maxSlidingWindow(int[] nums, int k) { if (nums null || nums.length 0) return new int[0]; int n nums.length; int[] res new int[n - k 1]; DequeInteger deque new ArrayDeque(); int idx 0; for (int i 0; i n; i) { // 1. 清理过期下标当前窗口左边界为 i - k 1 while (!deque.isEmpty() deque.peekFirst() i - k 1) { deque.pollFirst(); } // 2. 维护单调递减弹出队尾所有不大于当前值的下标 while (!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); } // 3. 当前下标入队 deque.offerLast(i); // 4. 窗口完整时记录答案 if (i k - 1) { res[idx] nums[deque.peekFirst()]; } } return res; } }这段代码有几个地方值得停下来细说。第一清理过期下标的时机。我习惯在“入队新元素之前”先清理队首过期元素这样保证队列里所有元素都是当前窗口的有效元素。也看到过有人后清理先入队再检查过期那样做其实也能AC但逻辑上没那么干净容易在连续弹出的时候判断出错。第二维护单调性时用的是而不是。也就是说当队尾元素值和新元素相等时我也会把队尾弹出去。这个细节很多人不理解我单独解释一下。两个相等值的元素新来的那个下标更大在滑动窗口里它存活的时间更久。既然值一样大旧元素能做的贡献新元素全部能做且新元素更晚离开窗口所以旧的相等元素对后续任何窗口都没有价值直接淘汰。如果用保留相等元素队列里会残留“值相同但下标更小”的元素它们虽然不影响当前窗口的最大值结果但会让队列长度更长在极端情况下比如数组中有大量连续重复值队列可能退化成 O(k) 的长度虽然复杂度依然是均摊 O(1)但没必要多占空间。第三记录答案的条件i k - 1。窗口从下标0开始覆盖但真正形成完整窗口需要右边界到达 k - 1。在这之前窗口不足k个元素队首虽然存在但它代表的窗口并不完整不能作为答案。很多新手容易在这里栽跟头把前 k - 1 个不完整窗口的结果也输出了。第四关于 ArrayDeque 的容量问题。Java 的 ArrayDeque 会自动扩容所以不需要手动管理大小。有人担心它不能存 null这里我们存的全是 int 下标没有 null 问题放心用。3.2 C 版本基于 dequeclass Solution { public: vectorint maxSlidingWindow(vectorint nums, int k) { int n nums.size(); vectorint res; dequeint dq; for (int i 0; i n; i) { while (!dq.empty() dq.front() i - k 1) { dq.pop_front(); } while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); } dq.push_back(i); if (i k - 1) { res.push_back(nums[dq.front()]); } } return res; } };C 的 deque 头文件是dequepop_front()和pop_back()分别对应头部和尾部弹出。这里有一个常见的坑很多人用queue而不是deque但queue只支持队首弹出、队尾插入无法从队尾弹出而我们的算法必须从队尾“淘汰”元素所以queue是做不到的。deque才是正确的容器选择。另外C 中如果对nums[dq.back()]和nums[i]的比较不小心把写成了在后续的答案正确性上一般不会出错但队列里会留着多余的相等元素调试的时候队列状态看起来会比较“脏”。我建议统一写成思路最清晰。3.3 Python 版本基于 collections.dequefrom collections import deque class Solution: def maxSlidingWindow(self, nums: List[int], k: int) - List[int]: n len(nums) if n 0 or k 0: return [] q deque() res [] for i in range(n): # 弹出过期下标 while q and q[0] i - k 1: q.popleft() # 维护单调递减 while q and nums[q[-1]] nums[i]: q.pop() q.append(i) if i k - 1: res.append(nums[q[0]]) return resPython 的deque支持下标访问q[0]、q[-1]使用起来最直观。要注意popleft()和pop()的区别前者从左边弹出对应过期元素清理后者从右边弹出对应维护单调性时的尾部淘汰。这两个方法名字容易搞混写的时候别把popleft()写成pop()否则行为完全不对。Python 还有一个优点deque可以在两端 O(1) 地插入删除底层是双向链表加块状数组的结构性能足够。如果你把队列换成普通 listq.pop(0)是 O(n) 的一旦 n 大了就会超时。3.4 复杂度到底是多少每个下标最多入队一次、出队一次入队出队都是 O(1)所以整个算法的时间复杂度是 O(n)。虽然代码里有两个 while 循环嵌套在 for 循环里但均摊分析下总操作次数不会超过 2n完全符合线性复杂度。空间复杂度是 O(k)因为队列里最多同时存在 k 个下标在极端情况下比如数组严格递减且没有过期元素时队列确实会装满 k 个元素。但在大多数情况下由于单调性维护会淘汰大量元素队列实际长度通常远小于 k。这个 O(n) 的复杂度比堆的 O(n log k) 整整下降了一个数量级。这也是为什么面试官在听到“优先队列”之后会追问“能不能优化”——单调队列就是这道题的最优解之一。4. 实战中的五个高频坑与排查心得4.1 队列存值而不是存下标这是我见过最多的初级错误。有人觉得既然队列里维护的是“候选最大值”那直接把值存进去不就行了问题在于“过期判断”必须依赖下标。窗口移动一步后左边界变成 i - k 1你需要知道队首元素的下标是否小于这个边界。如果队列里只有值你根本无从判断这个值到底属于哪个位置。举个例子窗口大小 k 3当前窗口覆盖 [2,3,4] 下标队列中可能存了一个很大的值 99但它是下标2的元素。下一次窗口变成 [3,4,5]下标2已经过期了。如果队列里只有 99 而没有下标你怎么知道它该不该被弹出没法知道。所以严格来说队列里必须存下标比较大小用 nums 做索引取值。4.2 while 和 if 的区别为什么要循环弹出维护单调性的时候很多人会写成一个if而不是while。这样写的问题在于队尾可能不止一个元素比新元素小如果只弹一个那队列仍然不满足单调递减后续的“队首即最大值”性质就被破坏了。比如队列现在是 [5, 3, 2]新元素是 4。如果只弹一个把2弹掉队列变成 [5, 3, 4]队尾 4 前面还有一个 3但它比 4 小。这样队列从队首到队尾是 5, 3, 4并不是单调递减的虽然队首还是5不影响当前窗口的答案但下一次新元素再来的时候这个不单调的队列会让“淘汰逻辑”出错——比如新元素是 6它会连续弹出4、3然后发现队首5也被淘汰队列清空最终结果还是对的但万一新元素是 4.5它把4弹掉队列变成 [5,3]看似没毛病但那个3明明比4.5小却被留在了队里它会在之后干扰判断。所以这里必须用while直到队尾元素大于当前值或者队列为空才停。这个细节我在面试别人的时候也经常看到属于“背代码没理解原理”的典型案例。4.3 过期清理和单调性维护的先后顺序两种顺序都能得到正确答案但我强烈建议先清理过期元素再插入新元素。原因是逻辑更清晰第一步确保队列中元素全在窗口内第二步处理单调性时才不会受到过期元素的干扰。如果你先入队新元素再清理过期元素可能会遇到一个隐藏问题新元素比队尾所有元素都大把队列清空后又入队此时队首是新元素本身它当然不是过期元素清理队首的循环条件对它不生效结果是对的。但假如新元素的值相当小它被直接追加到队尾紧接着清理过期元素的循环开始从队首弹这也不会有问题。所以两种顺序都能AC但先清理过期的写法更不容易在面试的紧张氛围里写错建议养成这个习惯。4.4 等于号的处理用 还是 前面已经提过我推荐在弹出队尾时使用。这里再展开解释一下利弊。假设数组是 [2, 1, 2]k 2。如果弹出条件用而不是过程是这样的i 0队列空入队0q [0]。i 1队尾0对应值1即 nums[0]2与 nums[1]1 比较2 1不弹入队1。q [0,1]。窗口完整队首值2记录2。i 2队尾1对应值1nums[2]2弹出条件如果是2 1 不成立不弹。然后检查过期左边界 i-k1 1队首0过期弹出0q [1]。再入队2q [1,2]。队首值是 nums[1]1记录1。但实际窗口是 [1,2]最大值应该是2。答案错误看到了吗这里问题不是出在等于号而是出在“旧的大元素已经过期”后没有及时用新元素淘汰掉那个值为1的元素。如果弹出条件用i2 时就会先弹出队尾的1再把2入队队首变成2答案就对了。从这个例子可以看出来在边界情况下用会导致队列中残留“值相等但下标更小”的元素一旦“更大的旧元素”过期这个残留的小值就可能顶上来充当最大值造成错误。所以务必使用。4.5 窗口未完整时没有延迟记录答案最后这个坑在初学者里非常普遍在第一层循环里前 k - 1 个元素进来时窗口长度不足 k但有同学会直接从 i 0 开始记录队首作为答案导致答案数组前面多出来好几个“伪最大值”。比如 nums [4, 1, 2, 3]k 3。如果从 i 0 就开始记录会输出 [4, 3, 2, 3] 这样的4个值但正确答案只需要 2 个值[4, 3]窗口[4,1,2]最大4窗口[1,2,3]最大3。所以一定要等 i k - 1 再开始记录结果。5. 滑动窗口思想的工程化延伸5.1 镜像问题滑动窗口最小值如果你理解了最大值版本的单调递减队列求最小值就是一分钟的事把队列维护成单调递增队首就是最小值弹出条件从“队尾值 当前值”改成“队尾值 当前值”其余完全一样。这个镜像问题在很多场景里都有用。比如股票的滚动最低价、系统日志在固定时间窗口内的最低延迟、机器学习里滑动窗口的特征归一化需要窗口内的 min 和 max等。其实力扣也有类似题目比如求滑动窗口中的最小值套上同一个模板就能秒掉。我这里给一个通用模板的记忆方式求最大值队列从头到尾递减大在前求最小值队列从头到尾递增小在前。判断队尾该不该弹就看新元素能不能“干掉”队尾——能干掉的标准就是队尾不再是“极值的候选者”。5.2 滑动窗口中位数为什么需要对顶堆滑动窗口中位数比最值复杂一个档次。中位数不是窗口的极值而是“中间位置”的值无法靠单调队列直接维护因为队列的单调性只能保证极值在两端保证不了中间值是哪个。常见做法是对顶堆一个大顶堆维护窗口左半部分的元素一个小顶堆维护右半部分的元素两个堆的大小始终维持着某种平衡比如大顶堆比小顶堆多1个或相等那么大顶堆的堆顶就是中位数。窗口移动时需要从对应的堆里删除离开的元素通常用延迟删除再插入新元素然后调整两个堆的平衡。整体复杂度 O(n log k)比求最值的 O(n) 要高这也是为什么中位数问题不能照搬单调队列。从热词里能看到“滑动窗口中位数”确实是一个被广泛搜索的高频痛点。如果你把239题的单调队列套路用在这里会发现根本行不通——所以遇到新题先想清楚问题的本质是“极值”还是“位置”再决定数据结构。5.3 硬件视角滑动窗口滤波和Verilog的窗口想法我注意到有很多搜索词是关于“滑动窗口滤波verilog”“滑动窗口滤波器延迟”的。这其实是硬件/信号处理领域里非常常见的需求在一个固定长度的采样窗口内计算均值、最大值、最小值等统计量用来做信号平滑或异常检测。软件算法里的单调队列思想在硬件实现上通常不会直接对应。FPGA上的滑动窗口滤波通常用移位寄存器shift register按周期存储采样值然后用组合逻辑并行计算窗口内所有数据的比较结果。每个时钟周期窗口滑动一次旧数据从寄存器链末端丢出新数据从输入端移入最大值通过一组比较器树comparator tree得到。从这个角度看“滑动窗口最大值”并不是纯软件练习题它在实时信号处理、传感器数据采集、金融指标计算等场景里都有影子。软件和硬件的差距在于软件用“淘汰不可能成为答案的元素”来降低复杂度硬件则用“并行计算所有元素”来保证每周期都输出结果。它们一个省时间一个换吞吐各有各的取舍。5.4 数组区间最大值查询的兄弟们热词里还有“n个数确定第k个最大值”“数组求区间最大值的算法题”这类搜索。它们是滑动窗口最大值题目的远房亲戚。“n个数确定第k个最大值”是 TopK 问题。如果 k 固定且远小于 n可以用大小为 k 的小顶堆维护“当前最大的k个元素”堆顶就是第 k 大的数。也可以用快速选择算法QuickSelect在平均 O(n) 时间内求出。这和滑动窗口最大值的思路不同——TopK 没有窗口移动的约束是静态集合的统计。“数组求区间最大值”则是一类更宽泛的问题。如果数组是静态的、大量任意区间查询用 ST表预处理后可以做到 O(1) 查询如果数组支持单点修改就需要线段树如果只是固定长度的滑动窗口才是单调队列的主场。选择哪种方案完全取决于你的操作模式是“查询多”“更新多”还是“窗口固定移动”。5.5 数据流场景与生产实践的启发热词中出现了“kafka 读写最大值与硬件关系”这种工程向的搜索。它和本题算法没有直接联系但指向一个更普遍的事实流式数据场景里我们经常需要在一段不断滑动的窗口中统计极值、均值、计数等。生产环境里常见的监控系统比如Prometheus的rate()函数、滑动窗口限流器固定窗口或滑动窗口统计请求速率、交易系统的滚动风险管理本质上都在做类似的事情维护一个不断向前移动的窗口计算窗口内的某种聚合值。这时候单调队列、前缀和、双指针这些“基础算法”就不仅仅是面试题而是真正能落地到线上系统的工具。比如实现一个滑动窗口限流器限制任意1秒内最多允许N个请求。你可以用一个队列记录每个请求的时间戳每次新请求来时把队列头部所有过期时间戳弹出然后看队列长度是否超过N。这其实就是“滑动窗口内计数”的经典实现和239题的“滑动窗口内最大值”共享同一套窗口维护思想。5.6 这道题还能怎么变形最后聊几个常见的变形帮助你把单调队列这个工具打磨得更锋利。第一个变形是“滑动窗口最大值最小值同时输出”。做法是同时维护一个单调递减队列和一个单调递增队列各自按规则更新。这个变形的价值在于很多滑动窗口优化题比如求“满足某某条件的最短子数组”需要同时知道窗口内的max和min来调整左右指针。第二个变形是“字符串滑动窗口”比如“无重复字符的最长子串”。这类题目不再用双端队列维护单调性而是用哈希表记录字符上一次出现的位置本质上还是窗口边界的动态管理。窗口思想是共通的但具体数据结构要因题而异。第三个变形是“多重滑动窗口”比如在二维矩阵里做固定大小子矩阵的最大值。这一类题通常需要两次单调队列先在每一行做一次滑动窗口最大值得到一个新矩阵再在每一列对新矩阵做一次滑动窗口最大值最终得到每个子矩阵的最大值。这个过程也被称为“二维滑动窗口最大值”是239题的经典高阶应用。这些变形题我在刷题和实际面试中都遇到过。如果能把239题的底层原理吃透这些变形题大多只是“套两层循环”和“换一下比较条件”的区别。6. 实操总结与个人体会我最早刷这道题的时候也想当然地用了优先队列然后被提示“能不能O(n)”彻底卡住。后来认真推了一遍单调队列的整个流程尤其亲自画了几个例子包括相等元素、极端递增递减序列之后才真正理解“为什么可以弹出队尾的较小元素”这件事的本质。从那之后很多窗口类的题目我都能秒联想到底层数据结构该用什么。据我个人的刷题经验这套模板有几个值得反复咀嚼的要点第一队列里存下标是铁律别偷懒存值第二弹出相等的旧元素是保证正确性的关键别省那个等号第三先清理过期再入队新元素是最好写也最好debug的顺位第四窗口完整才记录结果。这四点我称之为“239四诫”每次写到类似的题我都会在心里默念一遍。如果你正在准备面试我建议你不仅要把代码写熟还要能把“为什么双端队列能做到O(n)”这件事用两三句话讲清楚。面试官问这道题往往不只是考你会不会写还想看你能不能把他引到“单调性”“淘汰策略”“均摊分析”这些点上。你要是能主动提到“延迟无效元素”“下标生命周期”这些词面试体验会完全不一样。最后再分享一个调试技巧遇到边界用例不通过就在纸上把数组和队列的变化过程一行行列出来对标一下每一步的队首、队尾和答案。比如用 [1,-1,1,2,-3,3] 这种含负数、含相等值、含递增递减混合的数据跑三遍就基本能把所有隐藏bug挖出来。比对着代码瞪眼有效得多。