水果成篮

先想最直白的:从每棵树都试着往右摘到摘不动为止。能算对,但每个起点都重新扫一遍,数据一大就慢。下面看怎么省掉重复。

暴力 · 从下标 0 起摘：暴力第一趟:从下标 0 出发,先摘到 1,篮子里有种类 {1}。继续往右看。

暴力 · 起点 0 继续：摘到下标 2 的 3 时,种类变成 {1,2,3} 三种,超了!起点 0 这趟最多摘 [1,2] 长度 2。接着起点挪到 1 重头再扫——这就是重复劳动。

暴力 · 起点换成 1 重扫：起点挪到 1,前面的 0 号格不要了(变灰),又从头开始数种类:先摘 2,种类 {2}。注意 [1,2] 这段区间刚才已经数过一遍了,现在还要再数——重复就出在这。

暴力 · 起点 1 继续：起点 1 往右摘到下标 2 的 3,种类 {2,3} 两种,还合法,接着往右。

暴力 · 起点 1 摘到底：起点 1 这趟运气好,后面 2、2 都已在篮子里,一路只有 {2,3} 两种,摘到末尾长度 4。但要这样把每个起点都重扫一遍,n 大就是 O(n²)。下面看怎么只扫一遍。

关键发现:左右指针都只往右走、绝不回头。右指针每次进一个新水果,只有当种类超过 2 时,才从左边挤出水果。这样整排树只扫一遍 → O(n)。

盯住三样东西:左指针 l、右指针 r、还有计数表里的种类数。下面一帧一个动作走一遍 [1,2,3,2,2]。

起步 · 空窗口：开局两根指针 l、r 都停在 0,篮子还空着。接下来右指针每走一格,就把那格水果装进计数表。

r 入窗 · 装 1：右指针把 0 号格的 1 装进篮子,计数表 {1:×1},1 种 ≤ 2 合法。窗口 [0,0] 长 1,最长记 1。

r 右扩 → 1：r 右移到 1,把 2 装进来,计数表 {1:×1, 2:×1},正好 2 种,两个篮子都用上了,还合法。窗口长 2,最长更新成 2。

r 右扩 → 2 · 超标!：r 移到 2,把 3 装进来,计数表变 {1:×1, 2:×1, 3:×1} 三种,超过 2 个篮子!现在不能更新答案,得从左边挤水果,直到只剩 2 种。

缩左 ① · 左端 1 计数减 1：缩左第一步:看 l 当前指着的水果 1,把它的计数减 1 变 ×0。计数到 0 说明窗口里这种水果一个都不剩了,下一步该把这个键删掉。

缩左 ② · 删键 + l 右移：缩左第二步:把计数为 0 的 1 从表里删掉,l 右移到 1,0 号格被挤出变灰。计数表 {2:×1, 3:×1} 回到 2 种,窗口 [1,2] 重新合法,长 2。

r 右扩 → 3：r 移到 3,又是个 2,已经在篮子里,只是个数 +1,计数表 {2:×2, 3:×1},还是 2 种。窗口长 3,最长刷新成 3!

r 右扩 → 4：r 移到 4,还是 2,个数再 +1,计数表 {2:×3, 3:×1},仍是 2 种。窗口长到 4,最长刷新成 4!这就是答案区间 [2,3,2,2]。

r 到头 · 完成：r 走到数组末尾,结束。整趟下来最长合法窗口是 [1,4],绿色这四格 [2,3,2,2] 就是答案 4。l 和 r 各自只往右走了一遍。

再演一例 · [0,1,2,2]：换串 [0,1,2,2] 再走一遍。l、r 都在 0,装 0,计数 {0:×1},长 1。

r 右扩 → 1：r 到 1,装 1,计数 {0:×1, 1:×1},两种装满,长 2,最长记 2。

r 右扩 → 2 · 超标：r 到 2 装进 2,计数 {0:×1, 1:×1, 2:×1} 三种超标,得缩左。

缩左 · 挤掉 0：缩左把 l 处的 0 减到 ×0 并删键,l 右移到 1,计数回到 {1:×1, 2:×1},窗口 [1,2] 合法,长 2。

r 右扩 → 3 · 完成：r 到 3,又是 2 只是个数 +1,计数 {1:×1, 2:×2},长 3,最长刷成 3。绿色 [1,2,2] 就是这串的答案。

为什么是 O(n) 不是 O(n²)?因为 r 走 n 步,l 一辈子加起来也最多走 n 步,合计 2n 次操作——线性。这就是滑动窗口比暴力快的根。

雷区实演 · 忘记删键：假如缩左时把 1 减到 0 却忘了删键,计数表里还留着 {1:×0},种类数被误算成 3,窗口怎么缩都 >2 种,答案直接崩——这就是必须删键的原因。

边界三连：先想单棵(1)、全同种(4)、全不同(2)三种极端,代码就稳了。

面试追问：把「指针不回头 = O(n)」和「至多 K 种的通用模板」讲清楚,是这题面试的得分点。