小时候玩丢手绢最紧张的时刻不是手绢落地而是你要绕大半圈跑回自己位置时全场都在喊“跑快点”。现在回头看这个游戏的数学本质一点也不幼稚一圈孩子就是环形数组追与被追的最短路径就是两点在环上的最短距离而“手绢现在可能在谁身后、转一圈后落到哪”这类判断本质上就是对长度为 N 的环做定长扫描。把它映射到算法题里正好是标题里那两件事的组合滑动窗口 环形最优距离。这篇文章就以丢手绢为引子把环形数组上的滑动窗口问题从暴力解法一路讲到单调队列优化最后顺着热搜词把滑动窗口滤波、重传协议、verilog 实现一起串一遍目标是让你彻底搞懂这套思路遇到同类题能直接动手写代码。我用的是最朴素的方式理解它所有环形问题都是“直线问题 一个环回头的边界条件”。只要把这个边界处理对了剩下的滑动窗口模板可以原封不动地复用。下面按我的拆解顺序来。1. 为什么“丢手绢”是个值得认真拆解的算法题1.1 从游戏规则到环形数组定义清楚再动手丢手绢的规则很简单N 个人围成一个圈一个人拿着手绢在圈外跑趁某人不注意把手绢丢在他身后然后继续跑被丢中的人要捡起手绢追追到之前丢手绢的人要抢占被丢中者的空位。如果把每个人抽象成一个下标位置这个圈就是一个环形数组长度为 N下标 0 到 N-1下标 N 又回到 0。这样看丢手绢的人围着圈跑本质上就是沿着环形数组做遍历他跑到某个位置 i对应数组下标 i % N。这个抽象不是咬文嚼字。环形数组是很多算法题的高频底层结构它同时带出了两个经典子问题一个是两点之间的环形最优距离另一个是在环上连续扫描一段区间也就是滑动窗口。标题里的“丢手绢问题”恰恰把这两者揉在一起所以拿它当引子非常合适。在动手设计算法前一定要把问题定义清楚。我给自己定的问题是给定一个环形数组 nums长度为 N以及一个窗口大小 K。求所有长度为 K 的环形连续窗口中窗口内最小值为全局最小的那个窗口并返回该窗口中心位置距离下标 0 的环形最优距离。这个问题可以拆成三层第一层是“怎么处理环”第二层是“怎么高效求每个定长窗口的最小值”第三层是“怎么把窗口位置转成环上的最短距离”。后面几节就是按这个顺序展开的。1.2 环形最优距离的两副面孔“环形最优距离”这个词在不同的书里长得不一样但本质只有两副面孔。第一副面孔是两点之间的最短环距。环形数组下标 0 到 N-1 首尾相连位置 i 和位置 j 之间有两条路一条沿下标递增方向走距离是 |i - j|另一条反过来走距离是 N - |i - j|。真正的最短距离要取两者中的较小值dist(i, j) min(|i - j|, N - |i - j|)丢手绢里追的人从 B 的位置出发跑的方向和丢手绢的人一致丢手绢的人已经跑出半圈。谁赢取决于路程长短这个“路程”就是上面的公式。第二副面孔是沿环连续推进的总长度。假设手绢每轮向后传 K 个位置传了 t 轮最终位置是 (start K * t) % N。如果想回到起点附近本质上是在研究 K 和 N 的最大公约数这是另一个经典话题。回到本文我们关心的是定长 K 的窗口在环上滑动窗口起点从 0 到 N-1 连续移动正好就是滑动窗口的标准使用场景。所以当别人说起“环形最优距离”不要一头雾水。先问一句是两点在环上的最短路径还是沿环扫描覆盖的距离本文两种都会用到但在代码里主导的是第二种场景第一种作为结果计算。2. 破环为链处理环形数组的两种主流套路环形数组最别扭的地方是下标到头之后要跳回 0。滑动窗口要求“连续推进”所以第一件事就是把环展开成直线。常见的做法有两种下标取模和双倍数组拼接。2.1 下标取模最省内存但要注意索引漂移第一种做法是保留原始数组所有下标访问都用i % N来转。写起来是这个味道def get_value(nums, i): return nums[i % len(nums)]好处是零额外空间坏处是每次访问都带一次取模运算而且窗口边界判断容易出错。比如窗口左边界 left 和右边界 right 都可能在环形语义下出现“left 大于 right”的情况处理起来非常绕。我早年写环形队列相关代码时有一段时间坚持用取模法结果在“窗口终点跨过 N 的边界”上反复踩坑。比如一个窗口从下标 7 开始长度为 3N 7正常展开后覆盖的是下标 7、8、9取模后是 0、1、2。看起来没问题但如果要做“右指针 - 左指针 1 K”这类长度判断指针本身已经越过数组末尾不能直接拿原始下标算。每次都要额外判断代码可读性很差。取模法适合那些“遍历整圈”而不是“维护连续窗口”的场景比如单纯求环形数组里的下一个更大元素或者判断会不会绕回原点。一旦窗口要频繁移动我建议优先考虑拼接法。2.2 双倍数组拼接用空间换代码简洁第二种做法是把数组复制一份接在后面形成长度为 2N 的新数组arr nums nums这样原本的环形连续区间比如起点 6、长度 4 的窗口在展开数组里就是下标 6 到 9 的普通连续区间完全不需要考虑取模。滑动窗口的所有逻辑都和普通数组一模一样定位结果时再“映射回原下标”即可。代价是空间翻倍。N 是 10 万级时完全无所谓N 上亿时才需要考虑内存。实际刷题和业务开发里99% 的场景双倍数组拼接都够用而且代码更不容易写错。还有一个细节双倍数组里最多只需要枚举 N 个起点也就是窗口起点从 0 到 N-1。窗口终点会落在 N 到 2N-2 之间所以 arr 长度至少是 N K - 1。为了省事直接nums nums最稳妥长度 2N 必然覆盖。如果 K 小于 N只开 N K 的长度也够但这样做需要多写一个min我不推荐除非内存真的紧张。2.3 两种套路怎么选一张表说清楚我自己选型时参考这个标准维度下标取模双倍数组拼接额外空间O(1)O(N)代码可读性边界判断多易错线性逻辑清晰访问速度每次带取模运算直接数组索引适合场景只遍历一圈、不维护窗口滑动窗口、单调栈、区间统计窗口长度 K N需要额外取模处理 K同样需要处理 K但展开后逻辑不变如果只是“从某个起点开始走 K 步看看结果”用取模。如果要做“滑动窗口维护最值/和/频率”用拼接。丢手绢问题属于后者所以我下面的所有代码都默认走拼接路线。3. 从暴力到滑动环形最优距离的求解推演3.1 暴力解法每个窗口从头扫一遍有多痛最直接的想法是枚举每个窗口起点 i从 i 到 i K - 1 扫一遍找出这个窗口的最小值再和全局最优比较。def brute_force(nums, k): n len(nums) best_val float(inf) best_center -1 for start in range(n): cur_min float(inf) for j in range(k): idx (start j) % n cur_min min(cur_min, nums[idx]) if cur_min best_val: best_val cur_min center (start k // 2) % n best_center center return best_val, best_center每个窗口花费 O(K) 时间一共 N 个窗口整体 O(N*K)。当 K 接近 N/2 时复杂度接近 O(N^2/2)数据量一大就崩。暴力解的意义是帮我们验证正确性。我写算法的习惯是先写一个绝对不可能错的暴力版本再用优化版本去对拍。环形问题尤其需要因为边界条件太多直接上优化代码很容易“感觉对了但结果差一位”。3.2 滑动窗口的“复用”思想移一位只动两头观察暴力解可以发现窗口从起点 i 移到起点 i1 时新增的元素只有一个下标 iK移除的元素也只有一个下标 i。窗口内的其他 K-1 个元素完全没变。暴力解法无视这个事实每次都重新扫描全部 K 个元素白白浪费了大量重复计算。滑动窗口的核心思想就是复用先把上一个窗口的统计结果“带”过来然后做一次“减去旧元素 加入新元素”的增量更新。这个思想在生活中特别常见。比如你在窗口前看 10 个人的队伍想知道现在最矮的是谁队伍只往前走了一个人你只需要对比新来的那个人和之前最矮的人不可能回头把所有 10 个人再量一遍。滑动窗口就是这么干的。但这里有个微妙的问题如果窗口维护的是“和”增量更新很简单减去旧值、加上新值就行。如果维护的是“最小值”就没法用同样的方式因为你不知道被移除的那个元素到底是不是当前最小值。如果它刚好是最小值减掉它之后第二小的值是谁你并没有维护这个信息。这时就需要下一节的单调队列登场。3.3 固定窗口模板可直接抄的代码在引入单调队列之前先看一个“维护窗口和”的标准固定窗口模板感受一下基础结构。给定环形数组和窗口大小 K求所有环形窗口的和def circular_window_sum(nums, k): n len(nums) k k % n or n # 关键窗口超过一圈时收缩 arr nums nums window_sum sum(arr[:k]) res [window_sum] for i in range(1, n): window_sum arr[i k - 1] - arr[i - 1] res.append(window_sum) return res注意这里先做了k k % n or n也就是如果 K 能整除 N整个环都是窗口直接取全环和。这一步放在展开数组之前避免无意义的超大窗口。后面的for i in range(1, n)只枚举 N 个起点因为环形窗口的起点集合就是 0 到 N-1。这个模板值得背下来。它把三个容易出错的位置都固定好了窗口更新公式arr[i k - 1] - arr[i - 1]里的下标偏移只枚举前 N 个起点K 超过一圈时先取模。对“和”适用对“最值”不直接适用接下来就是单调队列的活儿。4. 单调队列才是真正的抓手窗口最值的 O(N) 解法4.1 为什么不用堆删除过期元素的代价看到“动态维护窗口最值”很多人第一反应是优先队列堆。堆的插入和取最值都是 O(log K)看起来可以接受。但问题在于窗口移动时被移出窗口的元素可能不在堆顶你想删它标准堆做不到“定点删除”只能懒标记删除元素过期先不管等到它成为堆顶时再弹出。懒标记的思路能过代码却容易绕。因为你不仅要记录值还要记录下标弹出时还得判断这个下标是否在窗口范围内。写多了就会发现这相当于手动实现了一个带过期时间的优先队列坑并不少。单调队列换了个角度它不维护所有 K 个元素而是只维护“可能成为窗口最小值”的候选元素。这个集合远比 K 小而且天然有序队头就是当前窗口的最小值过期元素直接从队头弹出一切都顺理成章。4.2 单调队列的维护逻辑核心就两条规则用双端队列 deque 存下标。以“求窗口最小值”为例两条规则新元素入队时把队尾所有“值不小于新元素”的下标全部弹出再把新下标压入队尾。这样队头到队尾的值是严格单调递增的队头就是当前窗口最小值。每次窗口右移后检查队头下标是否已经滑出窗口左边界如果是从队头弹出。第二条规则保证了队列里的元素都属于当前窗口第一条规则保证了队列里的元素“一个比一个更有资格当最小值”。仔细想想第二条规则和第一条规则的关系队头的值最小但如果队头过期了它必须走队头走后新队头就是剩下的候选中最小的。由于每个下标最多入队一次、出队一次总操作次数是 O(N)均摊到每次窗口移动只有 O(1)。这就是单调队列比暴力快得多的根本原因。丢掉手绢里就好比你只记住全场当前最矮的人以及“如果最矮的人走了谁可能是下一个最矮的”。你不需要记住所有人只需要记住一条潜在的“接替链”。4.3 完整实现与复杂度分析下面是我的完整解法直接解决第一节定义的问题求环形数组中所有长度为 K 的窗口的最小值并返回全局最小窗口的中心到下标 0 的最短环距。from collections import deque def circular_sliding_window_min(nums, k): n len(nums) k k % n if k 0: k n # 窗口等于整环 arr nums nums q deque() best_val float(inf) best_center -1 for i in range(n k - 1): # 只需扫到最后一个窗口终点 # 规则1保持队尾到队头单调递增 while q and arr[q[-1]] arr[i]: q.pop() q.append(i) # 规则2弹出过期下标窗口范围是 [i-k1, i] while q and q[0] i - k 1: q.popleft() # 当窗口已经完整时开始统计 if i k - 1: cur_min arr[q[0]] center_raw i - k 1 k // 2 # 窗口起点的中心位置展开数组中 center center_raw % n if cur_min best_val: best_val cur_min best_center center # 计算到下标0的最短环距 dist min(best_center, n - best_center) return best_val, best_center, dist nums [2, 5, -1, 4, 3, 6, 0] k 3 print(circular_sliding_window_min(nums, k)) # 输出(-1, 1, 1)结果解释所有长度为 3 的环形窗口中包含 -1 的窗口最小值都是 -1第一个达到该值的窗口中心是下标 1中心到下标 0 的最短环距是 1。这里有一个细节容易搞混center_raw i - k 1 k // 2中i - k 1是当前窗口的起点加k // 2得到窗口中心。因为是“环形中心”所以直接对 N 取模映射回原数组。如果只要“第一个最优窗口”那取模后的 center 可能有多个候选比如窗口起点 0 和起点 1 的中心可能都是同一个。实际按需调整即可。C 版骨架也顺手贴一下面试手写时节奏更快#include deque #include vector #include algorithm using namespace std; pairint, int circularWindowMin(vectorint nums, int k) { int n nums.size(); k % n; if (k 0) k n; vectorint arr nums; arr.insert(arr.end(), nums.begin(), nums.end()); dequeint q; int best INT_MAX, center -1; for (int i 0; i n k - 1; i) { while (!q.empty() arr[q.back()] arr[i]) q.pop_back(); q.push_back(i); while (!q.empty() q.front() i - k 1) q.pop_front(); if (i k - 1) { int val arr[q.front()]; int rawCenter (i - k 1 k / 2) % n; if (val best) { best val; center rawCenter; } } } return {best, center}; }复杂度方面每个下标最多入队一次、出队一次总时间 O(N)空间 O(N)展开数组 O(K)队列。相比暴力 O(N*K)当 N 和 K 都大时差距是数量级的。4.4 队列里存下标而不是存值这是新手最容易踩的坑单独提出来说。单调队列里应该存“下标”不是“值”。如果只存值队列弹出过期元素时根本不知道这个值对应哪个位置你无法判断它还在不在窗口里。如果存下标取最小值时用arr[q[0]]获取值判断过期时用q[0] i - k 1一个下标同时解决了“值”和“位置”两个需求。可以这么理解你在队伍里记住的不是“这个人身高 160”而是“这个位置的人身高 160”。前面的人走了你要知道该看下一个位置而不是盯着一个已经离开的人的身高。5. 顺着热词走一圈滑动窗口在滤波、重传、Verilog 里的真面目“滑动窗口”这四个字在不同圈子里指的东西不太一样但底层结构都是“一个固定长度的数据集合随着时间向前移动旧数据离开、新数据进入”。这也是为什么很多人搜“滑动窗口最小值”之后会连着搜出一堆滤波、重传协议、verilog 的内容。它们真的是同一个思想的工程化变种。5.1 滑动窗口滤波窗口越大越平滑延迟也越大滑动窗口滤波最常见的形态是滑动均值滤波。假设传感器采集到一串数据 x[0], x[1], ...要对第 n 个点做平滑取它前面 M 个点的平均值y[n] (x[n - M 1] x[n - M 2] ... x[n]) / M这个 M 就是窗口长度。在代码里用累加和的方式维护窗口每次前进一个点只需要window_sum new_value - old_value smoothed window_sum / M这就和环形数组滑动窗口求和完全一样了。我之前在嵌入式项目里对温湿度传感器的原始读数做这种滤波M 取 5 和取 20 的差别肉眼可见M 小曲线跟手但毛刺多M 大曲线顺滑但滞后明显。这里的“滞后”就是热搜词里说的“滑动窗口滤波器延迟”。延迟怎么算滑动均值滤波的输出实际上是窗口内 M 个点的平均如果拿输出序列和原始序列做对齐等效延迟是 (M - 1) / 2 个采样周期。M 越大平滑力度越强延迟越大。所以选 M 本质是在“平滑效果”和“实时性”之间做权衡这个权衡思路和算法题里 K 值的选择一模一样。如果窗口中混入了脉冲噪声比如传感器突然跳变一个尖峰均值滤波会把尖峰均摊到整个窗口效果一般。这时改用滑动中值滤波更稳窗口内排序取中间值。中值滤波的窗口最值维护同样可以用滑动窗口 有序结构来实现只不过比“最值”又复杂了一步。5.2 滑动窗口重传协议窗口是可靠性和吞吐率的平衡旋钮网络传输里的滑动窗口是另一种形态。发送端不用发一条等一条而是可以连续发出多个报文这些“已发送但尚未确认”的报文共同构成一个发送窗口。随着确认报文不断返回窗口整体前移就像滑动窗口算法里的左右指针一起向右移动。窗口大小直接决定吞吐率窗口越大同一时刻在途的数据越多链路利用率越高但窗口越大一旦出错需要重传的数据也越多接收端缓冲压力也越大。TCP 的流量控制、拥塞控制本质上都是在动态调节这个窗口。从数据结构角度发送窗口就是一对左右指针维护的区间每次收到一个 ACK左指针右移发送新数据时右指针右移。判断窗口满不满就是看右指针减左指针是否达到窗口上限。这和数组上的滑动窗口窗口大小判断完全同构只是窗口的左边界由“外部确认事件”驱动而不是由固定步长驱动。5.3 FPGA 里的滑动窗口verilog 实现的核心与坑FPGA 上做滑动窗口滤波常见的做法是用移位寄存器链实现窗口缓存。M 个寄存器排成一排每个时钟上升沿新数据从最左边进入所有数据向右移一位最右边的旧数据被移出。这样任意时刻M 个寄存器里正好存着最近 M 个采样点这就是一个硬件滑动窗口。求和部分可以用加法树并行计算如果窗口长度是 2 的幂比如 8、16、32除 M 的操作可以直接用右移节省逻辑资源。延迟计算也清晰从数据输入到输出滤波结果大约是 M 个时钟周期加上求和流水线的延迟。这里有个工程坑寄存器链搬移数据会导致功耗和布线压力成倍增长窗口一大就很吃力。更优雅的做法是用 FIFO 或双口 RAM 模拟滑动窗口读指针和写指针配合不搬移数据只更新读地址。我见过不少同学第一次写 verilog 滑动均值滤波直接把 M 个数据接成一长串加法器综合后时序根本收敛不了。用流水的加法树或者直接例化 DSP 单元才是实际可落地的方案。换句话说你在算法题里写的单调队列、双端队列落到 FPGA 上对应的是“如何高效维护窗口内最值/和”的硬件结构移位寄存器、FIFO 是不同成本下的工程取舍。理解了这层对应关系热词里的那些看似天差地别的词就串成一条线了。6. 环形窗口的三大坑与我的实战心得6.1 窗口大小超过一圈先取模再滑动环形数组上如果 K 大于 N窗口滑动起来会重复覆盖同一批元素。比如 N7、K10长度为 10 的窗口在环上扫实际内容等于长度为 10 % 7 3 的窗口再叠加若干整环。整环部分对极值没有影响因为一个环包含全部数组元素。所以处理方式很简单k k % n如果取模结果是 0说明 K 是 N 的整数倍窗口等于整个环直接返回全局最值即可。上面的代码里已经处理了这个逻辑。这个坑很容易被忽略因为小规模测试数据一般不会特意构造“窗口比环还长”的用例。我建议把k k % n or n这一行固定在模板里不要在业务代码里临时判断。6.2 下标映射展开位置和原位置之间的换算双倍数组拼接后所有窗口逻辑都是线性的但最终结果要映射回原环形数组。最容易出错的地方是“窗口中心位置”的映射。展开数组里的下标 raw_pos 可能是 N 或 2N 范围内的任意值映射回原下标只需要raw_pos % n。但要注意窗口中心本身有两种定义如果 K 是奇数中心唯一如果 K 是偶数中心有两个位置比如长度为 4 的窗口中心可以是下标偏左的第二个位置也可以是偏右的第三个位置。我在题目里取了k // 2作为中心偏移这是约定不是绝对答案。实际做题时一定要先确认题意要的是“窗口起点距离目标的距离”还是“窗口中心距离目标的距离”。同一个窗口起点、中心、终点的环距完全不同计算前先把定义写下来比什么都管用。6.3 调试环形滑窗的土办法环形问题为什么总写错因为大脑很难同时跟踪“虚拟下标”和“真实下标”。我的土办法是先在草稿纸上把展开数组完整写出来再手动推一遍前几个窗口的队列变化最后用暴力版本对拍。比如 nums [2, 5, -1, 4, 3, 6, 0], K 3展开数组是index: 0 1 2 3 4 5 6 7 8 9 value: 2 5 -1 4 3 6 0 2 5 -1窗口 [0, 1, 2] 最小值是 -1窗口 [1, 2, 3] 最小值是 -1窗口 [2, 3, 4] 最小值是 -1窗口 [3, 4, 5] 最小值是 3窗口 [4, 5, 6] 最小值是 0……手推一遍后再让代码打印q的内容核对很快就能定位是“过期弹出写错”还是“入队条件写错”。还一个小技巧代码里临时加点调试输出。比如每次窗口完整时打印i, q, arr[q[0]]和手推结果对照。修完再删掉不要留着。就我自己这段时间的经验来说环形滑动窗口题想写对真正重要的不是背模板而是把三个边界刻在脑子里K 和 N 的关系、展开下标与原始下标的换算、窗口中心定义的确认。这三件事在每一步代码里都可能出错但只要把暴力版本放在旁边当参照物耐心对拍一轮基本都能平稳落地。以后看到“环形 定长连续区间 最值/和”这类组合我不会再慌着套模板而是先在草稿纸上画一圈位置再决定取模还是拼接、用不用单调队列。思路清晰了代码自然就顺了。 
长河君 · 2026/10/10 20:34:02 · 阅读 1.2k 环形数组上的滑动窗口：从丢手绢到单调队列优化
小时候玩丢手绢最紧张的时刻不是手绢落地而是你要绕大半圈跑回自己位置时全场都在喊“跑快点”。现在回头看这个游戏的数学本质一点也不幼稚一圈孩子就是环形数组追与被追的最短路径就是两点在环上的最短距离而“手绢现在可能在谁身后、转一圈后落到哪”这类判断本质上就是对长度为 N 的环做定长扫描。把它映射到算法题里正好是标题里那两件事的组合滑动窗口 环形最优距离。这篇文章就以丢手绢为引子把环形数组上的滑动窗口问题从暴力解法一路讲到单调队列优化最后顺着热搜词把滑动窗口滤波、重传协议、verilog 实现一起串一遍目标是让你彻底搞懂这套思路遇到同类题能直接动手写代码。我用的是最朴素的方式理解它所有环形问题都是“直线问题 一个环回头的边界条件”。只要把这个边界处理对了剩下的滑动窗口模板可以原封不动地复用。下面按我的拆解顺序来。1. 为什么“丢手绢”是个值得认真拆解的算法题1.1 从游戏规则到环形数组定义清楚再动手丢手绢的规则很简单N 个人围成一个圈一个人拿着手绢在圈外跑趁某人不注意把手绢丢在他身后然后继续跑被丢中的人要捡起手绢追追到之前丢手绢的人要抢占被丢中者的空位。如果把每个人抽象成一个下标位置这个圈就是一个环形数组长度为 N下标 0 到 N-1下标 N 又回到 0。这样看丢手绢的人围着圈跑本质上就是沿着环形数组做遍历他跑到某个位置 i对应数组下标 i % N。这个抽象不是咬文嚼字。环形数组是很多算法题的高频底层结构它同时带出了两个经典子问题一个是两点之间的环形最优距离另一个是在环上连续扫描一段区间也就是滑动窗口。标题里的“丢手绢问题”恰恰把这两者揉在一起所以拿它当引子非常合适。在动手设计算法前一定要把问题定义清楚。我给自己定的问题是给定一个环形数组 nums长度为 N以及一个窗口大小 K。求所有长度为 K 的环形连续窗口中窗口内最小值为全局最小的那个窗口并返回该窗口中心位置距离下标 0 的环形最优距离。这个问题可以拆成三层第一层是“怎么处理环”第二层是“怎么高效求每个定长窗口的最小值”第三层是“怎么把窗口位置转成环上的最短距离”。后面几节就是按这个顺序展开的。1.2 环形最优距离的两副面孔“环形最优距离”这个词在不同的书里长得不一样但本质只有两副面孔。第一副面孔是两点之间的最短环距。环形数组下标 0 到 N-1 首尾相连位置 i 和位置 j 之间有两条路一条沿下标递增方向走距离是 |i - j|另一条反过来走距离是 N - |i - j|。真正的最短距离要取两者中的较小值dist(i, j) min(|i - j|, N - |i - j|)丢手绢里追的人从 B 的位置出发跑的方向和丢手绢的人一致丢手绢的人已经跑出半圈。谁赢取决于路程长短这个“路程”就是上面的公式。第二副面孔是沿环连续推进的总长度。假设手绢每轮向后传 K 个位置传了 t 轮最终位置是 (start K * t) % N。如果想回到起点附近本质上是在研究 K 和 N 的最大公约数这是另一个经典话题。回到本文我们关心的是定长 K 的窗口在环上滑动窗口起点从 0 到 N-1 连续移动正好就是滑动窗口的标准使用场景。所以当别人说起“环形最优距离”不要一头雾水。先问一句是两点在环上的最短路径还是沿环扫描覆盖的距离本文两种都会用到但在代码里主导的是第二种场景第一种作为结果计算。2. 破环为链处理环形数组的两种主流套路环形数组最别扭的地方是下标到头之后要跳回 0。滑动窗口要求“连续推进”所以第一件事就是把环展开成直线。常见的做法有两种下标取模和双倍数组拼接。2.1 下标取模最省内存但要注意索引漂移第一种做法是保留原始数组所有下标访问都用i % N来转。写起来是这个味道def get_value(nums, i): return nums[i % len(nums)]好处是零额外空间坏处是每次访问都带一次取模运算而且窗口边界判断容易出错。比如窗口左边界 left 和右边界 right 都可能在环形语义下出现“left 大于 right”的情况处理起来非常绕。我早年写环形队列相关代码时有一段时间坚持用取模法结果在“窗口终点跨过 N 的边界”上反复踩坑。比如一个窗口从下标 7 开始长度为 3N 7正常展开后覆盖的是下标 7、8、9取模后是 0、1、2。看起来没问题但如果要做“右指针 - 左指针 1 K”这类长度判断指针本身已经越过数组末尾不能直接拿原始下标算。每次都要额外判断代码可读性很差。取模法适合那些“遍历整圈”而不是“维护连续窗口”的场景比如单纯求环形数组里的下一个更大元素或者判断会不会绕回原点。一旦窗口要频繁移动我建议优先考虑拼接法。2.2 双倍数组拼接用空间换代码简洁第二种做法是把数组复制一份接在后面形成长度为 2N 的新数组arr nums nums这样原本的环形连续区间比如起点 6、长度 4 的窗口在展开数组里就是下标 6 到 9 的普通连续区间完全不需要考虑取模。滑动窗口的所有逻辑都和普通数组一模一样定位结果时再“映射回原下标”即可。代价是空间翻倍。N 是 10 万级时完全无所谓N 上亿时才需要考虑内存。实际刷题和业务开发里99% 的场景双倍数组拼接都够用而且代码更不容易写错。还有一个细节双倍数组里最多只需要枚举 N 个起点也就是窗口起点从 0 到 N-1。窗口终点会落在 N 到 2N-2 之间所以 arr 长度至少是 N K - 1。为了省事直接nums nums最稳妥长度 2N 必然覆盖。如果 K 小于 N只开 N K 的长度也够但这样做需要多写一个min我不推荐除非内存真的紧张。2.3 两种套路怎么选一张表说清楚我自己选型时参考这个标准维度下标取模双倍数组拼接额外空间O(1)O(N)代码可读性边界判断多易错线性逻辑清晰访问速度每次带取模运算直接数组索引适合场景只遍历一圈、不维护窗口滑动窗口、单调栈、区间统计窗口长度 K N需要额外取模处理 K同样需要处理 K但展开后逻辑不变如果只是“从某个起点开始走 K 步看看结果”用取模。如果要做“滑动窗口维护最值/和/频率”用拼接。丢手绢问题属于后者所以我下面的所有代码都默认走拼接路线。3. 从暴力到滑动环形最优距离的求解推演3.1 暴力解法每个窗口从头扫一遍有多痛最直接的想法是枚举每个窗口起点 i从 i 到 i K - 1 扫一遍找出这个窗口的最小值再和全局最优比较。def brute_force(nums, k): n len(nums) best_val float(inf) best_center -1 for start in range(n): cur_min float(inf) for j in range(k): idx (start j) % n cur_min min(cur_min, nums[idx]) if cur_min best_val: best_val cur_min center (start k // 2) % n best_center center return best_val, best_center每个窗口花费 O(K) 时间一共 N 个窗口整体 O(N*K)。当 K 接近 N/2 时复杂度接近 O(N^2/2)数据量一大就崩。暴力解的意义是帮我们验证正确性。我写算法的习惯是先写一个绝对不可能错的暴力版本再用优化版本去对拍。环形问题尤其需要因为边界条件太多直接上优化代码很容易“感觉对了但结果差一位”。3.2 滑动窗口的“复用”思想移一位只动两头观察暴力解可以发现窗口从起点 i 移到起点 i1 时新增的元素只有一个下标 iK移除的元素也只有一个下标 i。窗口内的其他 K-1 个元素完全没变。暴力解法无视这个事实每次都重新扫描全部 K 个元素白白浪费了大量重复计算。滑动窗口的核心思想就是复用先把上一个窗口的统计结果“带”过来然后做一次“减去旧元素 加入新元素”的增量更新。这个思想在生活中特别常见。比如你在窗口前看 10 个人的队伍想知道现在最矮的是谁队伍只往前走了一个人你只需要对比新来的那个人和之前最矮的人不可能回头把所有 10 个人再量一遍。滑动窗口就是这么干的。但这里有个微妙的问题如果窗口维护的是“和”增量更新很简单减去旧值、加上新值就行。如果维护的是“最小值”就没法用同样的方式因为你不知道被移除的那个元素到底是不是当前最小值。如果它刚好是最小值减掉它之后第二小的值是谁你并没有维护这个信息。这时就需要下一节的单调队列登场。3.3 固定窗口模板可直接抄的代码在引入单调队列之前先看一个“维护窗口和”的标准固定窗口模板感受一下基础结构。给定环形数组和窗口大小 K求所有环形窗口的和def circular_window_sum(nums, k): n len(nums) k k % n or n # 关键窗口超过一圈时收缩 arr nums nums window_sum sum(arr[:k]) res [window_sum] for i in range(1, n): window_sum arr[i k - 1] - arr[i - 1] res.append(window_sum) return res注意这里先做了k k % n or n也就是如果 K 能整除 N整个环都是窗口直接取全环和。这一步放在展开数组之前避免无意义的超大窗口。后面的for i in range(1, n)只枚举 N 个起点因为环形窗口的起点集合就是 0 到 N-1。这个模板值得背下来。它把三个容易出错的位置都固定好了窗口更新公式arr[i k - 1] - arr[i - 1]里的下标偏移只枚举前 N 个起点K 超过一圈时先取模。对“和”适用对“最值”不直接适用接下来就是单调队列的活儿。4. 单调队列才是真正的抓手窗口最值的 O(N) 解法4.1 为什么不用堆删除过期元素的代价看到“动态维护窗口最值”很多人第一反应是优先队列堆。堆的插入和取最值都是 O(log K)看起来可以接受。但问题在于窗口移动时被移出窗口的元素可能不在堆顶你想删它标准堆做不到“定点删除”只能懒标记删除元素过期先不管等到它成为堆顶时再弹出。懒标记的思路能过代码却容易绕。因为你不仅要记录值还要记录下标弹出时还得判断这个下标是否在窗口范围内。写多了就会发现这相当于手动实现了一个带过期时间的优先队列坑并不少。单调队列换了个角度它不维护所有 K 个元素而是只维护“可能成为窗口最小值”的候选元素。这个集合远比 K 小而且天然有序队头就是当前窗口的最小值过期元素直接从队头弹出一切都顺理成章。4.2 单调队列的维护逻辑核心就两条规则用双端队列 deque 存下标。以“求窗口最小值”为例两条规则新元素入队时把队尾所有“值不小于新元素”的下标全部弹出再把新下标压入队尾。这样队头到队尾的值是严格单调递增的队头就是当前窗口最小值。每次窗口右移后检查队头下标是否已经滑出窗口左边界如果是从队头弹出。第二条规则保证了队列里的元素都属于当前窗口第一条规则保证了队列里的元素“一个比一个更有资格当最小值”。仔细想想第二条规则和第一条规则的关系队头的值最小但如果队头过期了它必须走队头走后新队头就是剩下的候选中最小的。由于每个下标最多入队一次、出队一次总操作次数是 O(N)均摊到每次窗口移动只有 O(1)。这就是单调队列比暴力快得多的根本原因。丢掉手绢里就好比你只记住全场当前最矮的人以及“如果最矮的人走了谁可能是下一个最矮的”。你不需要记住所有人只需要记住一条潜在的“接替链”。4.3 完整实现与复杂度分析下面是我的完整解法直接解决第一节定义的问题求环形数组中所有长度为 K 的窗口的最小值并返回全局最小窗口的中心到下标 0 的最短环距。from collections import deque def circular_sliding_window_min(nums, k): n len(nums) k k % n if k 0: k n # 窗口等于整环 arr nums nums q deque() best_val float(inf) best_center -1 for i in range(n k - 1): # 只需扫到最后一个窗口终点 # 规则1保持队尾到队头单调递增 while q and arr[q[-1]] arr[i]: q.pop() q.append(i) # 规则2弹出过期下标窗口范围是 [i-k1, i] while q and q[0] i - k 1: q.popleft() # 当窗口已经完整时开始统计 if i k - 1: cur_min arr[q[0]] center_raw i - k 1 k // 2 # 窗口起点的中心位置展开数组中 center center_raw % n if cur_min best_val: best_val cur_min best_center center # 计算到下标0的最短环距 dist min(best_center, n - best_center) return best_val, best_center, dist nums [2, 5, -1, 4, 3, 6, 0] k 3 print(circular_sliding_window_min(nums, k)) # 输出(-1, 1, 1)结果解释所有长度为 3 的环形窗口中包含 -1 的窗口最小值都是 -1第一个达到该值的窗口中心是下标 1中心到下标 0 的最短环距是 1。这里有一个细节容易搞混center_raw i - k 1 k // 2中i - k 1是当前窗口的起点加k // 2得到窗口中心。因为是“环形中心”所以直接对 N 取模映射回原数组。如果只要“第一个最优窗口”那取模后的 center 可能有多个候选比如窗口起点 0 和起点 1 的中心可能都是同一个。实际按需调整即可。C 版骨架也顺手贴一下面试手写时节奏更快#include deque #include vector #include algorithm using namespace std; pairint, int circularWindowMin(vectorint nums, int k) { int n nums.size(); k % n; if (k 0) k n; vectorint arr nums; arr.insert(arr.end(), nums.begin(), nums.end()); dequeint q; int best INT_MAX, center -1; for (int i 0; i n k - 1; i) { while (!q.empty() arr[q.back()] arr[i]) q.pop_back(); q.push_back(i); while (!q.empty() q.front() i - k 1) q.pop_front(); if (i k - 1) { int val arr[q.front()]; int rawCenter (i - k 1 k / 2) % n; if (val best) { best val; center rawCenter; } } } return {best, center}; }复杂度方面每个下标最多入队一次、出队一次总时间 O(N)空间 O(N)展开数组 O(K)队列。相比暴力 O(N*K)当 N 和 K 都大时差距是数量级的。4.4 队列里存下标而不是存值这是新手最容易踩的坑单独提出来说。单调队列里应该存“下标”不是“值”。如果只存值队列弹出过期元素时根本不知道这个值对应哪个位置你无法判断它还在不在窗口里。如果存下标取最小值时用arr[q[0]]获取值判断过期时用q[0] i - k 1一个下标同时解决了“值”和“位置”两个需求。可以这么理解你在队伍里记住的不是“这个人身高 160”而是“这个位置的人身高 160”。前面的人走了你要知道该看下一个位置而不是盯着一个已经离开的人的身高。5. 顺着热词走一圈滑动窗口在滤波、重传、Verilog 里的真面目“滑动窗口”这四个字在不同圈子里指的东西不太一样但底层结构都是“一个固定长度的数据集合随着时间向前移动旧数据离开、新数据进入”。这也是为什么很多人搜“滑动窗口最小值”之后会连着搜出一堆滤波、重传协议、verilog 的内容。它们真的是同一个思想的工程化变种。5.1 滑动窗口滤波窗口越大越平滑延迟也越大滑动窗口滤波最常见的形态是滑动均值滤波。假设传感器采集到一串数据 x[0], x[1], ...要对第 n 个点做平滑取它前面 M 个点的平均值y[n] (x[n - M 1] x[n - M 2] ... x[n]) / M这个 M 就是窗口长度。在代码里用累加和的方式维护窗口每次前进一个点只需要window_sum new_value - old_value smoothed window_sum / M这就和环形数组滑动窗口求和完全一样了。我之前在嵌入式项目里对温湿度传感器的原始读数做这种滤波M 取 5 和取 20 的差别肉眼可见M 小曲线跟手但毛刺多M 大曲线顺滑但滞后明显。这里的“滞后”就是热搜词里说的“滑动窗口滤波器延迟”。延迟怎么算滑动均值滤波的输出实际上是窗口内 M 个点的平均如果拿输出序列和原始序列做对齐等效延迟是 (M - 1) / 2 个采样周期。M 越大平滑力度越强延迟越大。所以选 M 本质是在“平滑效果”和“实时性”之间做权衡这个权衡思路和算法题里 K 值的选择一模一样。如果窗口中混入了脉冲噪声比如传感器突然跳变一个尖峰均值滤波会把尖峰均摊到整个窗口效果一般。这时改用滑动中值滤波更稳窗口内排序取中间值。中值滤波的窗口最值维护同样可以用滑动窗口 有序结构来实现只不过比“最值”又复杂了一步。5.2 滑动窗口重传协议窗口是可靠性和吞吐率的平衡旋钮网络传输里的滑动窗口是另一种形态。发送端不用发一条等一条而是可以连续发出多个报文这些“已发送但尚未确认”的报文共同构成一个发送窗口。随着确认报文不断返回窗口整体前移就像滑动窗口算法里的左右指针一起向右移动。窗口大小直接决定吞吐率窗口越大同一时刻在途的数据越多链路利用率越高但窗口越大一旦出错需要重传的数据也越多接收端缓冲压力也越大。TCP 的流量控制、拥塞控制本质上都是在动态调节这个窗口。从数据结构角度发送窗口就是一对左右指针维护的区间每次收到一个 ACK左指针右移发送新数据时右指针右移。判断窗口满不满就是看右指针减左指针是否达到窗口上限。这和数组上的滑动窗口窗口大小判断完全同构只是窗口的左边界由“外部确认事件”驱动而不是由固定步长驱动。5.3 FPGA 里的滑动窗口verilog 实现的核心与坑FPGA 上做滑动窗口滤波常见的做法是用移位寄存器链实现窗口缓存。M 个寄存器排成一排每个时钟上升沿新数据从最左边进入所有数据向右移一位最右边的旧数据被移出。这样任意时刻M 个寄存器里正好存着最近 M 个采样点这就是一个硬件滑动窗口。求和部分可以用加法树并行计算如果窗口长度是 2 的幂比如 8、16、32除 M 的操作可以直接用右移节省逻辑资源。延迟计算也清晰从数据输入到输出滤波结果大约是 M 个时钟周期加上求和流水线的延迟。这里有个工程坑寄存器链搬移数据会导致功耗和布线压力成倍增长窗口一大就很吃力。更优雅的做法是用 FIFO 或双口 RAM 模拟滑动窗口读指针和写指针配合不搬移数据只更新读地址。我见过不少同学第一次写 verilog 滑动均值滤波直接把 M 个数据接成一长串加法器综合后时序根本收敛不了。用流水的加法树或者直接例化 DSP 单元才是实际可落地的方案。换句话说你在算法题里写的单调队列、双端队列落到 FPGA 上对应的是“如何高效维护窗口内最值/和”的硬件结构移位寄存器、FIFO 是不同成本下的工程取舍。理解了这层对应关系热词里的那些看似天差地别的词就串成一条线了。6. 环形窗口的三大坑与我的实战心得6.1 窗口大小超过一圈先取模再滑动环形数组上如果 K 大于 N窗口滑动起来会重复覆盖同一批元素。比如 N7、K10长度为 10 的窗口在环上扫实际内容等于长度为 10 % 7 3 的窗口再叠加若干整环。整环部分对极值没有影响因为一个环包含全部数组元素。所以处理方式很简单k k % n如果取模结果是 0说明 K 是 N 的整数倍窗口等于整个环直接返回全局最值即可。上面的代码里已经处理了这个逻辑。这个坑很容易被忽略因为小规模测试数据一般不会特意构造“窗口比环还长”的用例。我建议把k k % n or n这一行固定在模板里不要在业务代码里临时判断。6.2 下标映射展开位置和原位置之间的换算双倍数组拼接后所有窗口逻辑都是线性的但最终结果要映射回原环形数组。最容易出错的地方是“窗口中心位置”的映射。展开数组里的下标 raw_pos 可能是 N 或 2N 范围内的任意值映射回原下标只需要raw_pos % n。但要注意窗口中心本身有两种定义如果 K 是奇数中心唯一如果 K 是偶数中心有两个位置比如长度为 4 的窗口中心可以是下标偏左的第二个位置也可以是偏右的第三个位置。我在题目里取了k // 2作为中心偏移这是约定不是绝对答案。实际做题时一定要先确认题意要的是“窗口起点距离目标的距离”还是“窗口中心距离目标的距离”。同一个窗口起点、中心、终点的环距完全不同计算前先把定义写下来比什么都管用。6.3 调试环形滑窗的土办法环形问题为什么总写错因为大脑很难同时跟踪“虚拟下标”和“真实下标”。我的土办法是先在草稿纸上把展开数组完整写出来再手动推一遍前几个窗口的队列变化最后用暴力版本对拍。比如 nums [2, 5, -1, 4, 3, 6, 0], K 3展开数组是index: 0 1 2 3 4 5 6 7 8 9 value: 2 5 -1 4 3 6 0 2 5 -1窗口 [0, 1, 2] 最小值是 -1窗口 [1, 2, 3] 最小值是 -1窗口 [2, 3, 4] 最小值是 -1窗口 [3, 4, 5] 最小值是 3窗口 [4, 5, 6] 最小值是 0……手推一遍后再让代码打印q的内容核对很快就能定位是“过期弹出写错”还是“入队条件写错”。还一个小技巧代码里临时加点调试输出。比如每次窗口完整时打印i, q, arr[q[0]]和手推结果对照。修完再删掉不要留着。就我自己这段时间的经验来说环形滑动窗口题想写对真正重要的不是背模板而是把三个边界刻在脑子里K 和 N 的关系、展开下标与原始下标的换算、窗口中心定义的确认。这三件事在每一步代码里都可能出错但只要把暴力版本放在旁边当参照物耐心对拍一轮基本都能平稳落地。以后看到“环形 定长连续区间 最值/和”这类组合我不会再慌着套模板而是先在草稿纸上画一圈位置再决定取模还是拼接、用不用单调队列。思路清晰了代码自然就顺了。