刷过“水果成篮”这道题的人八成和我第一次一样看着题面觉得是一场果园采摘模拟写起来却发现左一个坑右一个坑。题目说的是一排果树按顺序长着每棵树上结一种编号的水果你手里有两个篮子每个篮子只能装一种水果从任意一棵树开始摘摘的过程中只能一直往右走一旦遇到第三种水果就必须停下问最多能摘多少棵树的果子。听起来像模拟题实际上是典型的滑动窗口而且是可变长度、以合法性为条件的滑动窗口。我一开始的思路很简单维护两个变量记录当前正在摘的两种水果编号遇到第三种就清空重来。这个想法在小例子上完全没问题一提交就露馅。这篇文章不打算只给一个能通过的代码我会把从“朴素重置”到“正确收缩窗口”的思考过程讲清楚尤其是 left 指针到底该怎么挪以及为什么网上很多用哈希表计数的写法在边界上容易翻车。1. 把水果成篮翻译成人话题目到底在让我们干什么1.1 题面还原两个篮子、连续采摘和水果编号题目给一个数组 fruitsfruits[i] 表示第 i 棵树上的水果种类编号。两个篮子意味着你最多只能同时接受两种不同编号第三种编号出现时你手里的两个篮子一定装不下。从任意位置开始只能连续往右采摘一旦前方出现第三种水果就必须停止。目标只有一个让采摘数量最大化。换句话说这题是在找一个连续子数组子数组里不同元素的个数不超过 2并且这个子数组的长度要尽量长。比如 [1,2,1,2,3]答案应该是 4取前四棵 [1,2,1,2]最后一棵是 3已经是第三种水果装不下所以不能算进去。再比如 [1,2,3,2,2]答案是 4取 [2,3,2,2]从下标 1 开始摘。这里有个容易被忽视的点“连续”两个字非常关键。它意味着你不能跳过某棵树去摘后面的果子也不能从整排树里挑出所有喜欢的水果。这个限制直接把问题定位成子数组问题而不是子序列问题。很多人一开始没想清楚这一点跑去排序或者做全局计数方向就错了。还有一点两个篮子装的不是“两个水果”而是“两种编号的同种水果可以装无数个”。理解了这个再看窗口里的计数逻辑就顺了。1.2 为什么朴素遍历不靠谱从“所有起点都试一遍”到N方复杂度把题面直接翻译成代码最朴素的做法是枚举起点 i从 i 开始向右扩展维护一个计数器统计窗口内出现了几种水果直到种类数超过 2 就停止记录当前长度。每个起点都这样跑一遍取最大长度。这个做法的问题是复杂度太高。如果数组长度是 n枚举起点是 O(n)每次向右扩展最坏又要 O(n)再加上判断种类数可能还要 O(n)整体轻轻松松到 O(n^2) 甚至 O(n^3)。实际题目数据规模通常到 10^5 这个量级O(n^2) 基本超时根本跑不动。所以我们需要的是每个元素尽量只被处理常数次总复杂度 O(n)。滑动窗口正好能做到这一点。窗口可以理解成数组上一个连续区间右边界不断向前扩展左边界只有在必要时向前移动。每个元素最多进窗口一次、出窗口一次总体线性。用一句话概括思路与其枚举所有可能的起点不如维护一个“当前合法区间”让右端点一直往前走左端点只在条件被破坏时跟进。顺便说一句这类题的核心就两个问题窗口的合法性条件是什么窗口收缩时数据怎么更新。对水果成篮来说合法性条件是窗口内不同水果编号数不超过 2更新策略是 right 每次向右扩一格然后收缩左边界直到窗口重新合法最后记录长度。这套骨架理解透了后面很多类似题目都能套。2. 滑动窗口的状态设计哈希表计数与“只记两种水果”的陷阱2.1 窗口内应该维护什么信息滑动窗口要能正确判断合法性就得维护足够的信息。水果成篮常见的做法有三种第一种是哈希表计数用 HashMap 记录窗口里每种水果的出现次数某一种次数归零就把它从表里删掉第二种是数组计数如果水果编号范围不大用数组替代哈希表省掉哈希开销第三种是只记录两种水果的最后出现位置利用“最多两种”这个限制省掉计数但实现时容易在细节上翻车。哈希表计数最直观也最不容易错。核心逻辑是右指针遍历数组把新水果加入计数只要窗口内种类数大于 2就移动左指针把左指针指向的水果计数减一减到 0 就删除收缩结束后窗口一定合法这时更新答案。这里要特别强调一个细节收缩条件要用 while 而不是 if。因为左指针移动一次窗口里可能还残留很多同一种水果种类数可能仍然大于 2必须连续移动直到真正回到合法状态。用 if 的话窗口在异常庞大的用例下会漏收缩答案直接算错。2.2 经典的“第三棵树”陷阱为什么不能简单重置窗口很多人第一版写法是发现第三种水果就把左边界跳到当前位置从新水果重新开始。这个想法听上去很合理——反正旧的两种水果里肯定有一种要被丢掉不如干脆都丢掉从新水果开始重新积累。但这个直觉是错的。丢掉哪一种不是由“谁先出现”决定的而是由“谁先断档”决定的。看一个最经典的反例[1,2,1,2,3]。如果遇到最后那个 3 时选择重置窗口从下标 4 开始重新摘窗口就只剩 [3]答案是 1而正确答案是 4也就是前四棵 [1,2,1,2]。这个反例直接否定了“重置整个窗口”的做法。再看一个反例[1,2,3,2,2]。正确答案是 4取 [2,3,2,2]对应下标 1 到 4。如果遇到下标 2 的水果 3 时重置窗口从下标 2 开始最多只能得到 [3,2,2]长度 3照样错。实际上正确的做法不是把旧的两种水果全部丢弃而是只丢弃一种、保留另一种继续延伸。窗口左指针不是随便跳到 right而是要跳到“被丢弃那种水果最后一次出现位置之后”。理解了这个才算真正摸到这道题的门道。下面我会展开讲 left 到底该怎么挪。3. left指针的移动艺术收缩窗口的时机与边界3.1 怎么判断该丢哪一种水果比较“最后出现位置”当第三种水果出现时窗口里一共有三种编号但篮子里只能放两种。这时候必须选择保留两种、丢弃一种。关键问题是丢弃哪一种答案是丢最后一次出现位置更靠前的那一种。原因其实很朴素右边界继续向右推进时窗口会不断纳入新元素。如果一种水果在窗口内最后一次出现的位置比较靠左说明它和当前右边界之间已经隔了一段没有这种水果的区域。从现在这个时刻往回看它的“连续性”已经断掉了。如果你还想保留它左边界就必须越过它最后一次出现的位置那它实际上已经不在窗口里了如果不越过窗口里又会混入第三种水果违法。所以唯一合理的选择就是放弃最后出现位置更靠前的水果把左边界直接移到最后出现位置再加一。我拿一个具体例子走一遍。[1,2,1,2,3]当遍历到下标 4 的水果 3 时窗口里的两种旧水果是 1 和 2。水果 1 的最后出现位置是下标 2水果 2 的最后出现位置是下标 3。比较之后1 更靠前所以丢弃 1左边界跳到下标 3也就是“最后一个 1 的位置 1”。新窗口变成 [2,3]合法。此时虽然答案只有 2但前四棵 [1,2,1,2] 已经在上一轮被记录过了不会丢解。所以在“最后出现位置”方案中left 的移动不是一步一步挪而是直接跳到指定下标。代码上通常写成 left Math.min(lastPos[a], lastPos[b]) 1同时把被丢弃的那种水果替换成新遇到的水果。3.2 先收缩再统计标准模板的步骤顺序不能乱滑动窗口的代码顺序看起来很简单但顺序一旦写错结果就是错的。标准顺序是三步第一right 向右走一步把新水果纳入窗口第二窗口可能因为引入新水果而非法进入收缩阶段移动 left 直到窗口重新合法第三收缩结束后窗口一定合法此时用 right - left 1 更新答案。为什么要先收缩再更新因为答案是“合法窗口的最大长度”。如果在收缩前就用右边界减左边界加一算出来的可能是一个包含三种水果的非法窗口虽然它更长但那种情况根本摘不了那么多所以不能参与比较。有人图省事发现第三种水果后不移动 left直接更新答案同样会错因为窗口还没回到合法状态。如果你用“不断缩小的左边界”那种 while 写法顺序尤其重要必须先把 left 指向的水果计数减一再判断这个水果是不是已经清零清零就删除最后才 left 加一。不少新手把 left 加一写在前面while 循环收缩的位置就全错了因为 left 已经变了减计数的对象却还是旧下标整个过程乱套。3.3 边界情况单种水果、全相同数组与空数组数组为空时直接返回 0这个不用多说。数组里只有一种水果或者所有水果编号都相同窗口从头到尾都合法left 永远不动答案就是数组长度 n。这两种情况在哈希表计数法下天然成立不需要特判。需要注意的反而是 left 移动过程中的边界当某一种水果的计数被减到 0 时一定要把它从哈希表里删除不能留着。否则后续判断 len(count) 2 时会把已经不在窗口里的水果也算进去导致窗口收缩不彻底。这个 bug 我见过不少次而且小样例不容易暴露只有在窗口反复出现同一种水果的用例里才会炸出来属于那种“测试一次通过、提交却超时代码永远跑不对”的隐蔽问题。4. 从水果成篮看滑动窗口家族和最大值最小值单调队列的关系4.1 滑动窗口模板的本质什么时候能用水果成篮属于“可变长度 合法性条件”的滑动窗口。这类题有一个共性要求一个连续区间使得某个条件成立同时希望区间尽可能长或尽可能短。通用的骨架是右指针遍历数组每次加入一个元素左指针在条件不满足时向前移动直到条件重新满足每轮记录最优结果。这个骨架能成立的前提是条件具备单调性窗口扩大时“条件满足”的难度只会增大窗口缩小时条件只会更容易满足。水果成篮里窗口变大时水果种类数只会增加不会减少所以一旦超过 2唯一能把它救回来的方式就是收缩左边界。如果条件不具备这种单调性滑动窗口会失效得回头换其他结构。单调性还有个隐含价值它保证 left 向右移动的过程中不会漏解。因为当 left 已经移动到某个位置说明窗口在 left 之前的所有起点以当前 right 结尾时都已经不合法而以后 right 继续增大这些起点只会更加不合法所以可以放心放弃。想明白了这一点你就会理解为什么滑动窗口不用回溯。4.2 同样的名字不同的结构最大值/最小值为什么用单调队列热搜词里有一堆“滑动窗口最小值/最大值”“单调队列-滑动窗口”这些和水果成篮虽然都叫滑动窗口但用的数据结构完全不同。固定大小窗口求最值比如窗口长度固定为 k每次右移一格要求快速拿到窗口内的最大值。如果每次扫描窗口求 max复杂度是 O(nk)数据一大会超时。单调队列的思路是维护一个双端队列队列里的元素在窗口内按值单调递减或递增队头就是窗口最大值。每次窗口右移时从队尾弹出那些“不可能再成为最大值”的旧元素从队头弹出已经离开窗口的元素每个元素进队出队各一次总复杂度 O(n)。水果成篮的哈希表计数解决的是“窗口内有哪些元素、每种有多少个”这是维持合法性的工具单调队列解决的是“窗口内元素的最值是哪个”这是做聚合查询的工具。一个是约束条件一个是统计极值两者不要混淆。4.3 其他领域里的“窗口”重传协议和滤波器的类比“滑动窗口”这个词在计算机网络和信号处理里也很常见比如滑动窗口重传协议、滑动窗口滤波模型、滑动窗口滤波 Verilog 实现。这些地方说的“窗口”和算法题里的窗口有完全同构的意象一个容量有限的区间随着时间推进旧元素离开、新元素进入对外输出对当前窗口内数据的某种聚合结果。差异在于用途。网络协议里的窗口控制的是“允许发送多少个未确认报文”信号处理里的滑动窗口是对一段信号做滤波或卷积平均而算法题里的滑动窗口是为了在一个数组上高效维护某个条件。拿生活化的比喻来说滑动窗口像你排队时不断向前移动的一段视野你只关心当前看到的一小段队伍队伍往前走窗口内容也更新。水果成篮要求这段视野里最多出现两种人最大值问题要求这段视野固定长度并记录最高的人。理解了这层意象再看各种“滑动窗口”就不会被名词吓到。5. 实战手记边界条件、实现取舍与踩坑清单5.1 HashMap计数法与双变量法的取舍先给最推荐的实现HashMap 计数法直观、通用、不容易错。代码我写成 Python方便阅读from collections import defaultdict def total_fruit(fruits): count defaultdict(int) left 0 ans 0 for right, fruit in enumerate(fruits): count[fruit] 1 while len(count) 2: left_fruit fruits[left] count[left_fruit] - 1 if count[left_fruit] 0: del count[left_fruit] left 1 ans max(ans, right - left 1) return ans这个版本的优点是它把“窗口内有哪些水果、每种多少个”完整记录下来收缩条件写起来和题目描述一一对应。推广到“最多 K 种水果”时只需要把 while len(count) 2 改成 while len(count) K一行搞定。双变量法也很经典只维护两种水果以及它们各自最后一次出现的位置left 一次跳到位省内存但代码可读性差、逻辑容易出错。我不建议在需要快速写出正确答案的场景用它它更适合作为理解 left 指针思想的一个练习。如果非要用双变量法记得每轮更新答案时窗口长度是 right - left 1而不是两种水果最后位置之差加一因为还要考虑 left 可能比某个最后位置更大。5.2 高频误区小结第一个误区是忘记删除计数归零的水果。哈希表里保留一个计数为 0 的键表面上不影响当前轮但下一轮判断 len(count) 时就会多算最终导致窗口收缩不到位。第二个误区是收缩顺序写反。正确顺序是“先减计数再判断是否为零并删除最后 left 加一”。如果先把 left 加一再去减计数减的是新下标的计数窗口收缩完全失效。第三个误区是把“遇到第三种水果就重置”当成正确答案。前面已经用 [1,2,1,2,3] 和 [1,2,3,2,2] 两个反例说明过重置会漏掉很多可行区间。第四个误区是答案更新时机不对。必须等窗口回到合法状态后再更新而不是刚发现第三种水果时就用当前 right 和旧 left 算长度。非法窗口的长度再大也不能算数。第五个误区是只测少量样例就提交。至少要把“只有一种水果”“所有水果都相同”“两种水果交替出现最后来一个第三种”这三类用例跑一遍再来验证复杂度行为。5.3 从水果成篮延伸最多K种水果、最小窗口与统计变体水果成篮可以轻松泛化成“最多 K 种不同元素的最长连续子数组”把 while len(count) 2 改成 while len(count) K 即可。这个思路在“至多两个不同字符的最长子串”这类题里完全同构把水果编号换成字符就行代码都不用大改。另一个相反的问题是“包含所有 K 种元素的最短窗口”比如求最短子串包含所有指定字符。这时框架相同但细节反过来了right 扩展时窗口从条件不满足走向满足一旦满足就要收缩 left 试图缩短窗口更新答案的时机是“刚刚满足条件”而不是“收缩后”。这类问题在字符串处理、日志关键字统计里很常见想清楚“合法条件”和“更新时机”理解水果成篮之后基本就能顺藤摸瓜。另外如果水果编号范围不大可以用数组代替哈希表维护计数或最后位置访问更快、内存更稳定但编号范围很大时数组方案直接爆炸还是老老实实用哈希表。工程上要根据数据范围选不能一套方案走天下。最后说点个人感受。我最初刷水果成篮时总想把滑动窗口背成模板后来发现模板只是壳真正有用的是想清楚两个问题窗口的合法性条件是什么窗口收缩时数据要怎样更新。对这道题合法性条件是“种类数不超过 2”收缩时不是简单重置而是把最早断档的那种水果去掉。想明白这一点代码怎么写都顺。如果你刷题时也卡在 left 指针上建议不要急着背答案把一个具体反例手写一遍看看 left 到底应该跳到哪。把这一步做扎实滑动窗口这类的题你基本就过关了。
水果成篮题解：滑动窗口与left指针移动详解
刷过“水果成篮”这道题的人八成和我第一次一样看着题面觉得是一场果园采摘模拟写起来却发现左一个坑右一个坑。题目说的是一排果树按顺序长着每棵树上结一种编号的水果你手里有两个篮子每个篮子只能装一种水果从任意一棵树开始摘摘的过程中只能一直往右走一旦遇到第三种水果就必须停下问最多能摘多少棵树的果子。听起来像模拟题实际上是典型的滑动窗口而且是可变长度、以合法性为条件的滑动窗口。我一开始的思路很简单维护两个变量记录当前正在摘的两种水果编号遇到第三种就清空重来。这个想法在小例子上完全没问题一提交就露馅。这篇文章不打算只给一个能通过的代码我会把从“朴素重置”到“正确收缩窗口”的思考过程讲清楚尤其是 left 指针到底该怎么挪以及为什么网上很多用哈希表计数的写法在边界上容易翻车。1. 把水果成篮翻译成人话题目到底在让我们干什么1.1 题面还原两个篮子、连续采摘和水果编号题目给一个数组 fruitsfruits[i] 表示第 i 棵树上的水果种类编号。两个篮子意味着你最多只能同时接受两种不同编号第三种编号出现时你手里的两个篮子一定装不下。从任意位置开始只能连续往右采摘一旦前方出现第三种水果就必须停止。目标只有一个让采摘数量最大化。换句话说这题是在找一个连续子数组子数组里不同元素的个数不超过 2并且这个子数组的长度要尽量长。比如 [1,2,1,2,3]答案应该是 4取前四棵 [1,2,1,2]最后一棵是 3已经是第三种水果装不下所以不能算进去。再比如 [1,2,3,2,2]答案是 4取 [2,3,2,2]从下标 1 开始摘。这里有个容易被忽视的点“连续”两个字非常关键。它意味着你不能跳过某棵树去摘后面的果子也不能从整排树里挑出所有喜欢的水果。这个限制直接把问题定位成子数组问题而不是子序列问题。很多人一开始没想清楚这一点跑去排序或者做全局计数方向就错了。还有一点两个篮子装的不是“两个水果”而是“两种编号的同种水果可以装无数个”。理解了这个再看窗口里的计数逻辑就顺了。1.2 为什么朴素遍历不靠谱从“所有起点都试一遍”到N方复杂度把题面直接翻译成代码最朴素的做法是枚举起点 i从 i 开始向右扩展维护一个计数器统计窗口内出现了几种水果直到种类数超过 2 就停止记录当前长度。每个起点都这样跑一遍取最大长度。这个做法的问题是复杂度太高。如果数组长度是 n枚举起点是 O(n)每次向右扩展最坏又要 O(n)再加上判断种类数可能还要 O(n)整体轻轻松松到 O(n^2) 甚至 O(n^3)。实际题目数据规模通常到 10^5 这个量级O(n^2) 基本超时根本跑不动。所以我们需要的是每个元素尽量只被处理常数次总复杂度 O(n)。滑动窗口正好能做到这一点。窗口可以理解成数组上一个连续区间右边界不断向前扩展左边界只有在必要时向前移动。每个元素最多进窗口一次、出窗口一次总体线性。用一句话概括思路与其枚举所有可能的起点不如维护一个“当前合法区间”让右端点一直往前走左端点只在条件被破坏时跟进。顺便说一句这类题的核心就两个问题窗口的合法性条件是什么窗口收缩时数据怎么更新。对水果成篮来说合法性条件是窗口内不同水果编号数不超过 2更新策略是 right 每次向右扩一格然后收缩左边界直到窗口重新合法最后记录长度。这套骨架理解透了后面很多类似题目都能套。2. 滑动窗口的状态设计哈希表计数与“只记两种水果”的陷阱2.1 窗口内应该维护什么信息滑动窗口要能正确判断合法性就得维护足够的信息。水果成篮常见的做法有三种第一种是哈希表计数用 HashMap 记录窗口里每种水果的出现次数某一种次数归零就把它从表里删掉第二种是数组计数如果水果编号范围不大用数组替代哈希表省掉哈希开销第三种是只记录两种水果的最后出现位置利用“最多两种”这个限制省掉计数但实现时容易在细节上翻车。哈希表计数最直观也最不容易错。核心逻辑是右指针遍历数组把新水果加入计数只要窗口内种类数大于 2就移动左指针把左指针指向的水果计数减一减到 0 就删除收缩结束后窗口一定合法这时更新答案。这里要特别强调一个细节收缩条件要用 while 而不是 if。因为左指针移动一次窗口里可能还残留很多同一种水果种类数可能仍然大于 2必须连续移动直到真正回到合法状态。用 if 的话窗口在异常庞大的用例下会漏收缩答案直接算错。2.2 经典的“第三棵树”陷阱为什么不能简单重置窗口很多人第一版写法是发现第三种水果就把左边界跳到当前位置从新水果重新开始。这个想法听上去很合理——反正旧的两种水果里肯定有一种要被丢掉不如干脆都丢掉从新水果开始重新积累。但这个直觉是错的。丢掉哪一种不是由“谁先出现”决定的而是由“谁先断档”决定的。看一个最经典的反例[1,2,1,2,3]。如果遇到最后那个 3 时选择重置窗口从下标 4 开始重新摘窗口就只剩 [3]答案是 1而正确答案是 4也就是前四棵 [1,2,1,2]。这个反例直接否定了“重置整个窗口”的做法。再看一个反例[1,2,3,2,2]。正确答案是 4取 [2,3,2,2]对应下标 1 到 4。如果遇到下标 2 的水果 3 时重置窗口从下标 2 开始最多只能得到 [3,2,2]长度 3照样错。实际上正确的做法不是把旧的两种水果全部丢弃而是只丢弃一种、保留另一种继续延伸。窗口左指针不是随便跳到 right而是要跳到“被丢弃那种水果最后一次出现位置之后”。理解了这个才算真正摸到这道题的门道。下面我会展开讲 left 到底该怎么挪。3. left指针的移动艺术收缩窗口的时机与边界3.1 怎么判断该丢哪一种水果比较“最后出现位置”当第三种水果出现时窗口里一共有三种编号但篮子里只能放两种。这时候必须选择保留两种、丢弃一种。关键问题是丢弃哪一种答案是丢最后一次出现位置更靠前的那一种。原因其实很朴素右边界继续向右推进时窗口会不断纳入新元素。如果一种水果在窗口内最后一次出现的位置比较靠左说明它和当前右边界之间已经隔了一段没有这种水果的区域。从现在这个时刻往回看它的“连续性”已经断掉了。如果你还想保留它左边界就必须越过它最后一次出现的位置那它实际上已经不在窗口里了如果不越过窗口里又会混入第三种水果违法。所以唯一合理的选择就是放弃最后出现位置更靠前的水果把左边界直接移到最后出现位置再加一。我拿一个具体例子走一遍。[1,2,1,2,3]当遍历到下标 4 的水果 3 时窗口里的两种旧水果是 1 和 2。水果 1 的最后出现位置是下标 2水果 2 的最后出现位置是下标 3。比较之后1 更靠前所以丢弃 1左边界跳到下标 3也就是“最后一个 1 的位置 1”。新窗口变成 [2,3]合法。此时虽然答案只有 2但前四棵 [1,2,1,2] 已经在上一轮被记录过了不会丢解。所以在“最后出现位置”方案中left 的移动不是一步一步挪而是直接跳到指定下标。代码上通常写成 left Math.min(lastPos[a], lastPos[b]) 1同时把被丢弃的那种水果替换成新遇到的水果。3.2 先收缩再统计标准模板的步骤顺序不能乱滑动窗口的代码顺序看起来很简单但顺序一旦写错结果就是错的。标准顺序是三步第一right 向右走一步把新水果纳入窗口第二窗口可能因为引入新水果而非法进入收缩阶段移动 left 直到窗口重新合法第三收缩结束后窗口一定合法此时用 right - left 1 更新答案。为什么要先收缩再更新因为答案是“合法窗口的最大长度”。如果在收缩前就用右边界减左边界加一算出来的可能是一个包含三种水果的非法窗口虽然它更长但那种情况根本摘不了那么多所以不能参与比较。有人图省事发现第三种水果后不移动 left直接更新答案同样会错因为窗口还没回到合法状态。如果你用“不断缩小的左边界”那种 while 写法顺序尤其重要必须先把 left 指向的水果计数减一再判断这个水果是不是已经清零清零就删除最后才 left 加一。不少新手把 left 加一写在前面while 循环收缩的位置就全错了因为 left 已经变了减计数的对象却还是旧下标整个过程乱套。3.3 边界情况单种水果、全相同数组与空数组数组为空时直接返回 0这个不用多说。数组里只有一种水果或者所有水果编号都相同窗口从头到尾都合法left 永远不动答案就是数组长度 n。这两种情况在哈希表计数法下天然成立不需要特判。需要注意的反而是 left 移动过程中的边界当某一种水果的计数被减到 0 时一定要把它从哈希表里删除不能留着。否则后续判断 len(count) 2 时会把已经不在窗口里的水果也算进去导致窗口收缩不彻底。这个 bug 我见过不少次而且小样例不容易暴露只有在窗口反复出现同一种水果的用例里才会炸出来属于那种“测试一次通过、提交却超时代码永远跑不对”的隐蔽问题。4. 从水果成篮看滑动窗口家族和最大值最小值单调队列的关系4.1 滑动窗口模板的本质什么时候能用水果成篮属于“可变长度 合法性条件”的滑动窗口。这类题有一个共性要求一个连续区间使得某个条件成立同时希望区间尽可能长或尽可能短。通用的骨架是右指针遍历数组每次加入一个元素左指针在条件不满足时向前移动直到条件重新满足每轮记录最优结果。这个骨架能成立的前提是条件具备单调性窗口扩大时“条件满足”的难度只会增大窗口缩小时条件只会更容易满足。水果成篮里窗口变大时水果种类数只会增加不会减少所以一旦超过 2唯一能把它救回来的方式就是收缩左边界。如果条件不具备这种单调性滑动窗口会失效得回头换其他结构。单调性还有个隐含价值它保证 left 向右移动的过程中不会漏解。因为当 left 已经移动到某个位置说明窗口在 left 之前的所有起点以当前 right 结尾时都已经不合法而以后 right 继续增大这些起点只会更加不合法所以可以放心放弃。想明白了这一点你就会理解为什么滑动窗口不用回溯。4.2 同样的名字不同的结构最大值/最小值为什么用单调队列热搜词里有一堆“滑动窗口最小值/最大值”“单调队列-滑动窗口”这些和水果成篮虽然都叫滑动窗口但用的数据结构完全不同。固定大小窗口求最值比如窗口长度固定为 k每次右移一格要求快速拿到窗口内的最大值。如果每次扫描窗口求 max复杂度是 O(nk)数据一大会超时。单调队列的思路是维护一个双端队列队列里的元素在窗口内按值单调递减或递增队头就是窗口最大值。每次窗口右移时从队尾弹出那些“不可能再成为最大值”的旧元素从队头弹出已经离开窗口的元素每个元素进队出队各一次总复杂度 O(n)。水果成篮的哈希表计数解决的是“窗口内有哪些元素、每种有多少个”这是维持合法性的工具单调队列解决的是“窗口内元素的最值是哪个”这是做聚合查询的工具。一个是约束条件一个是统计极值两者不要混淆。4.3 其他领域里的“窗口”重传协议和滤波器的类比“滑动窗口”这个词在计算机网络和信号处理里也很常见比如滑动窗口重传协议、滑动窗口滤波模型、滑动窗口滤波 Verilog 实现。这些地方说的“窗口”和算法题里的窗口有完全同构的意象一个容量有限的区间随着时间推进旧元素离开、新元素进入对外输出对当前窗口内数据的某种聚合结果。差异在于用途。网络协议里的窗口控制的是“允许发送多少个未确认报文”信号处理里的滑动窗口是对一段信号做滤波或卷积平均而算法题里的滑动窗口是为了在一个数组上高效维护某个条件。拿生活化的比喻来说滑动窗口像你排队时不断向前移动的一段视野你只关心当前看到的一小段队伍队伍往前走窗口内容也更新。水果成篮要求这段视野里最多出现两种人最大值问题要求这段视野固定长度并记录最高的人。理解了这层意象再看各种“滑动窗口”就不会被名词吓到。5. 实战手记边界条件、实现取舍与踩坑清单5.1 HashMap计数法与双变量法的取舍先给最推荐的实现HashMap 计数法直观、通用、不容易错。代码我写成 Python方便阅读from collections import defaultdict def total_fruit(fruits): count defaultdict(int) left 0 ans 0 for right, fruit in enumerate(fruits): count[fruit] 1 while len(count) 2: left_fruit fruits[left] count[left_fruit] - 1 if count[left_fruit] 0: del count[left_fruit] left 1 ans max(ans, right - left 1) return ans这个版本的优点是它把“窗口内有哪些水果、每种多少个”完整记录下来收缩条件写起来和题目描述一一对应。推广到“最多 K 种水果”时只需要把 while len(count) 2 改成 while len(count) K一行搞定。双变量法也很经典只维护两种水果以及它们各自最后一次出现的位置left 一次跳到位省内存但代码可读性差、逻辑容易出错。我不建议在需要快速写出正确答案的场景用它它更适合作为理解 left 指针思想的一个练习。如果非要用双变量法记得每轮更新答案时窗口长度是 right - left 1而不是两种水果最后位置之差加一因为还要考虑 left 可能比某个最后位置更大。5.2 高频误区小结第一个误区是忘记删除计数归零的水果。哈希表里保留一个计数为 0 的键表面上不影响当前轮但下一轮判断 len(count) 时就会多算最终导致窗口收缩不到位。第二个误区是收缩顺序写反。正确顺序是“先减计数再判断是否为零并删除最后 left 加一”。如果先把 left 加一再去减计数减的是新下标的计数窗口收缩完全失效。第三个误区是把“遇到第三种水果就重置”当成正确答案。前面已经用 [1,2,1,2,3] 和 [1,2,3,2,2] 两个反例说明过重置会漏掉很多可行区间。第四个误区是答案更新时机不对。必须等窗口回到合法状态后再更新而不是刚发现第三种水果时就用当前 right 和旧 left 算长度。非法窗口的长度再大也不能算数。第五个误区是只测少量样例就提交。至少要把“只有一种水果”“所有水果都相同”“两种水果交替出现最后来一个第三种”这三类用例跑一遍再来验证复杂度行为。5.3 从水果成篮延伸最多K种水果、最小窗口与统计变体水果成篮可以轻松泛化成“最多 K 种不同元素的最长连续子数组”把 while len(count) 2 改成 while len(count) K 即可。这个思路在“至多两个不同字符的最长子串”这类题里完全同构把水果编号换成字符就行代码都不用大改。另一个相反的问题是“包含所有 K 种元素的最短窗口”比如求最短子串包含所有指定字符。这时框架相同但细节反过来了right 扩展时窗口从条件不满足走向满足一旦满足就要收缩 left 试图缩短窗口更新答案的时机是“刚刚满足条件”而不是“收缩后”。这类问题在字符串处理、日志关键字统计里很常见想清楚“合法条件”和“更新时机”理解水果成篮之后基本就能顺藤摸瓜。另外如果水果编号范围不大可以用数组代替哈希表维护计数或最后位置访问更快、内存更稳定但编号范围很大时数组方案直接爆炸还是老老实实用哈希表。工程上要根据数据范围选不能一套方案走天下。最后说点个人感受。我最初刷水果成篮时总想把滑动窗口背成模板后来发现模板只是壳真正有用的是想清楚两个问题窗口的合法性条件是什么窗口收缩时数据要怎样更新。对这道题合法性条件是“种类数不超过 2”收缩时不是简单重置而是把最早断档的那种水果去掉。想明白这一点代码怎么写都顺。如果你刷题时也卡在 left 指针上建议不要急着背答案把一个具体反例手写一遍看看 left 到底应该跳到哪。把这一步做扎实滑动窗口这类的题你基本就过关了。
