搜这道题的时候我敢打赌你大概率刷到过一堆奇怪的东西docker search redis 报了个 500、MeiliSearch 在宝塔里怎么配、Bing 的 search host 又丢了、还有什么同人作品镜像站的搜索页……因为题目名字里带着一个 Search搜索引擎们就自动把所有沾边内容全给你端上来了。但 Codeforces 上的 C. Dora and Search 和这些东西八竿子打不着它是非常经典的一道双指针题核心只有一句话把不可能是答案的端点一个接一个扔掉剩下的区间自然就是答案。这题说的是给你一个长度为 n 的排列 a里面恰好是 1 到 n 各一次。让你找一对 l、r满足 1 ≤ l ≤ r ≤ n并且 a[l] 和 a[r] 这两个端点都不能是子数组 a[l..r] 里的最小值也不能是最大值。说白了区间首尾两个人谁都不能是这一组里最矮或者最高的那个。如果找得到输出任意一组 l、r找不到输出 -1。这题的定位很适合刚学完双指针、想练从两端收缩套路的选手。它不需要线段树、不需要 ST 表、不需要二分前置知识只有排列的性质和 while 循环里的边界判断。下面我从题意拆到证明再给完整代码和踩坑记录争取让你看完之后不仅会写还能把“为什么这么做不错”讲清楚。1. 这道题到底在问什么1.1 先用大白话把条件再抠一遍很多人读完题就急着写代码结果连端点不能是极值这个条件都没尝透。假设你手上有一个排列 a[3,1,6,2,5,4]。如果取 l1、r6整个区间的最小值是 a[2]1最大值是 a[3]6两个端点分别是 3 和 4都在值域中间所以答案是 1 6。如果取 l2、r6左端点是 1正好是区间最小值这就不合法。这个条件有两个层次要注意。第一区间内部怎么乱都无所谓只有两个端点有约束第二两个端点必须同时满足“不是最小也不是最大”只要有一个端点踩中极值整个区间就废。很多人写判断条件时只检查了左端点或者只检查了右端点这是最常见的逻辑漏点。另外题目没有要求输出字典序最小的答案也没有要求输出所有答案它只要任意一组合法的 l、r。这意味着你的算法只要保证“找到了就输出确实存在就一定找得到”不用操心多解问题反而给了双指针收缩很大的操作空间。1.2 先别被题目名字带偏名字里带 Search很多人第一反应是去找各种搜索算法模板二分、DFS、BFS、KMP、字符串哈希……全套翻一遍也没找到对应的地方然后心态就崩了。我甚至见过有人认真思考“这道题是不是要用搜索回溯枚举所有区间”完全跑偏。其实这里的 Search 是 Dora 这个角色在“寻找”一对合法边界它考察的是两个能力第一你能不能发现“全局最值可以通过收缩端点逐个排除”这个性质第二你能不能把双指针从常见的“滑窗维护合法窗口”迁移到“从两端向内剥除非法端点”的新场景。这个迁移才是这题真正的考点跟任何搜索引擎、任何字符串匹配算法都没关系。顺带提醒一句如果你去搜题解记得在关键词后面加上 Codeforces 或者题号否则很容易被一堆“带 Search 的热词”干扰。这个我在文末还会再展开。2. 从暴力到双指针的思路演进2.1 暴力枚举为什么撑不过 n2e5最直白的思路是枚举所有 l、r然后用一个能快速查询区间最值的数据结构判断端点是不是极值。假设你写了一个完美 RMQ能 O(1) 查询任意区间最值枚举区间对的数量本身就有 n(n1)/2n2e5 的时候大概是 2e10 量级跑完整个比赛时间都不够用。退一步固定左端点往右扫右端点顺便维护当前区间的最小值和最大值效率能提高到 O(n²)。但你会发现判断条件和两个端点耦合在一起右端点挪一格区间最小值可能变最大值也可能变左端点又可能从“中间值”变成“极值”。想用单调队列维护滑动窗口最值单调队列适用于固定长度的窗口而这里要求的是任意长度区间直接套不进来。这个复杂度困境不是出题人在难为你而是在逼你注意一个隐藏前提a 是排列。如果是普通数组允许重复值“排除一个最小值之后下一个最小值是谁”这件事就完全不确定了。排列保证了每个数字只出现一次这才让下一步的收缩策略有了坚实的落脚点。2.2 排列带来的三个关键性质排列这个条件能带来三个特别有用的性质。第一个性质最直白全局最小值一定是 1全局最大值一定是 n不需要任何预处理就能写进代码里。第二个性质是由于每个数只出现一次当某个最小值从区间里消失后剩下的数里最小的一定是“还没被排除掉的那个最小正整数”。说人话就是只要当前最小值 low 被移出区间新的最小值必然朝 low1 的方向变不会突然蹦出个 low2。第三个性质更隐蔽但更关键如果某个端点等于当前区间的最小值或最大值那么以它为端点的任意区间这个端点都必然是这个区间的极值。换句话说这种端点永远不可能出现在合法答案里。这个判断是局部的不需要看整个区间的内部结构只需要知道当前区间的最小值和最大值就能决定要不要扔掉它。这三个性质加在一起直接指向一个方案从两端同时往里收缩自己维护“当前区间的最值”发现端点是极值就扔掉然后更新最值。整个过程不需要额外数据结构。2.3 抓住全局最值双指针就有戏了现在思路已经很清晰了。维护当前考察区间 [l, r]同时维护它的最小值 low 和最大值 high。初始时整个排列最小值是 1、最大值是 n。下一步是不断检查两端如果 a[l] 等于 low说明左端点就是当前区间最小值它不可能成为合法区间的左端点于是 l 右移一位low 变成 low1如果 a[l] 等于 high同理l 右移一位high 变成 high-1右边的情况完全对称a[r] 等于 low 或 high 时r 左移一位并同步更新 low 或 high。一直重复直到左端点不是 low 也不是 high同时右端点也不是 low 也不是 high。这时候两个端点都严格夹在 [low, high] 中间而当前区间的所有元素也都落在这个范围内所以它们既不是区间最小值也不是最大值直接输出 l、r 就是答案。如果指针撞到一起还没找到说明无解输出 -1。这个思路最反直觉的地方是我们明明要找的是“端点不是区间极值”的区间判断时却只看端点是不是“全局剩下区间的极值”。原因是经过前面的排除当前区间的极值已经和全局剩下的极值对齐了二者是同一个东西。这个“不变式”是整个算法的基石下一节我专门拆开讲。3. 双指针收缩算法的完整设计3.1 维护 low 和 high 的真实含义很多题解只给代码不解释 low 和 high 的身份导致读者只能背模板。这里我多说几句。low 和 high 并不是随便从 1、n 出发往中间靠的两个计数器它们严格等于当前区间 [l, r] 中的最小值和最大值。这是一个贯穿整个算法的不变式。初始时显然成立整个排列的最小值是 1最大值是 n。看一次收缩如果 a[l]low说明 low 这个值被移出区间。因为排列里没有重复值剩下的元素里不可能再有 low又因为所有比 low 小的值如果存在早就在之前的收缩中被移走了否则 low 不会成为当前最小值所以新区间的最小值只能是 low1。同理如果 a[r]high新最大值只能是 high-1。于是每次收缩之后不变式继续成立。这个角度还能解释另一个问题为什么只检查端点“等于 low 或 high”就够了不需要检查端点是否落在 [low, high] 之外因为不可能落在外面。所有小于 low、大于 high 的值都必须经过端点位置才能被移出区间而一旦移出low/high 就已经跟着更新了。所以当前区间里剩下的元素全部都在 [low, high] 范围内。端点只有三种状态等于 low、等于 high、或者落在中间。前两种直接淘汰最后一种就是我们要找的目标。3.2 收缩规则四种情况一次讲清把收缩规则整理成一张清晰的表后面写代码时直接对照。记当前区间为 [l, r]当前最小值为 low最大值为 high。每一轮循环看四个条件如果 a[l] 等于 low左端点是区间最小值执行 l、low。如果 a[l] 等于 high左端点是区间最大值执行 l、high--。如果 a[r] 等于 low右端点是区间最小值执行 r--、low。如果 a[r] 等于 high右端点是区间最大值执行 r--、high--。如果四个条件都不命中输出 l 和 r结束。这里有一个容易忽略的细节一轮循环里可能先处理了左端点右端点马上就变成极值了也可能处理完右端点之后左端点又可疑了。所以这五个分支不能只在循环里跑一遍就完事必须放在 while 循环里反复跑直到要么输出答案要么 lr。写成伪代码大概是这样的l 1, r n low 1, high n while l r: if a[l] low: l, low else if a[l] high: l, high-- else if a[r] low: r--, low else if a[r] high: r--, high-- else: print(l, r) return print(-1)分支之间的顺序其实无所谓因为每轮最多执行一个分支下一轮循环会重新检查全部条件。重要的是“每轮至少执行一次移动”不能出现“端点都合法却没输出”的情况——那正是我们要找的答案必须当场输出。3.3 正确性证明为什么不会漏解只说“贪心收缩肯定没问题”是不够的我把它讲透。假设存在一个合法区间 [L, R]。算法一开始的区间 [1, n] 一定包含它。看算法某一步面对区间 [l, r]如果 lL说明要移掉的左端点在整个答案区间的左侧属于答案区间外的元素移掉它不会破坏“当前区间仍然包含 [L, R]”这个事实所以可以放心移。难的是 lL 的情况。这时左端点就是答案区间的左端点。合法的 [L, R] 要求 a[L] 既不是该区间的最小值也不是最大值。又因为 [L, R] 包含在当前区间 [l, r] 里而当前区间的最小值是 low、最大值是 high所以 a[L] 一定严格落在 low 和 high 之间它既不会等于 low也不会等于 high。于是算法的收缩条件对左端点根本不成立算法不可能因为“a[l] 等于 low 或 high”而误删它。右边同理。因此只要存在合法解算法在真正碰到它之前绝不会把它的端点移掉。一旦当前区间恰好缩到 [L, R]四个收缩条件全都不满足算法必然输出这个区间。反过来如果不存在合法解算法最终会把区间缩到 lr然后输出 -1。完整性和正确性就都有了。3.4 边界条件lr 和 -1 的判定容易踩的边界是循环条件。我第一版实现里就写成了 while(lr)结果程序要么输出 -1要么数组越界。原因很简单当 lr 时区间只有一个元素这个唯一的元素既是最大值又是最小值绝不可能满足“端点不是极值”的要求所以合法答案必须满足 lr。循环条件用 while(lr)一旦 lr 就说明没有合法区间直接输出 -1。另一个边界是收缩和 low/high 的同步问题。有人会把更新写乱a[l]low 时 l 加了low 却没加下一轮判断还在用旧的最小值整个状态就错位了。还有人会把所有 if 改成 if-else 链之后不再用 while 包住整个逻辑只跑一遍漏掉“移完左侧之后右侧又变成极值”的情况。边界问题拿数据说最直观。试 a[2,1,3]。初始 l1、r3、low1、high3。a[l]2 既不等于 low 也不等于 high于是看右端a[r]3 等于 high执行 r--、high2。现在 l1、r2、low1、high2。a[l]2 等于 high执行 l、high1。此时 l2、r2循环结束输出 -1。手动枚举也确实找不到合法区间说明这个结论是对的。这种小数据手跑一遍比任何口头解释都管用。4. 代码实现与踩坑实录4.1 C 参考实现含注释直接给一份能跑过的 C17 代码。输入输出用的是关同步的 cin/cout2e5 的数据量完全没压力没必要用 printf 硬造。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { int n; cin n; vectorint a(n 1); for (int i 1; i n; i) cin a[i]; int l 1, r n; int low 1, high n; bool found false; while (l r) { if (a[l] low) { l; low; } else if (a[l] high) { l; --high; } else if (a[r] low) { --r; low; } else if (a[r] high) { --r; --high; } else { cout l r \n; found true; break; } } if (!found) cout -1 \n; } return 0; }代码量不超过三十行。变量名 low/high 表示当前区间最小值和最大值l/r 表示两个端点。每次移动端点对应的 low/high 也同步移动保证下一轮判断仍然准确。用 found 标记是否已经输出过答案最后统一处理 -1可以避免一个测试用例里出现重复输出。4.2 四个最容易写错的细节第一个坑把 low/high 的更新和指针移动拆开写。比如先改 low 再移动 l从逻辑上说没错但很容易在中间插入调试语句时搞混变量状态。最稳的写法是紧凑形式把两件事写在同一行语义一目了然。第二个坑忘记题目给的是排列。如果数组允许重复“端点等于当前最小值”不代表它不能成为合法端点因为区间内部可能还有另一个相同的最小值。这个算法只对排列成立很多人把模板背下来拿去套非排列题结果全错。第三个坑把外层循环写成 while(true)靠 break 退出然后忘记处理 lr 的情况导致数组越界。实际上 while(lr) 这个条件本身就在挡边界不要轻易改成死循环。每次移动之后指针距离近一步最终一定会走到 lr。第四个坑多组测试数据时low/high/l/r 忘记在每个用例里重置。这些变量都是在循环体内初始化的正常情况下没问题但要小心把 low 初始化成 0 之类的笔误。我见过第一组样例能过、第二组开始全部错乱的解法问题就出在这种看似不起眼的初始值上。4.3 复杂度与替代方案对比时间复杂度 O(n)因为每次循环至少移动左指针或右指针一个位置总共最多移动 n 次。空间复杂度 O(n) 用于存输入数组除了这个数组之外只用到了常数额外空间。有人会想既然要判断区间最值干脆扔个 multiset 或者线段树进去每次移动端点时删除和插入元素维护当前区间的最值这当然也能 AC但复杂度变成 O(nlogn)。在 n2e5 时 O(nlogn) 也能过只是代码量、常数和思维量都大不少。更重要的是线段树解法会掩盖这题真正想让你发现的排列性质。我把几种常见方案放在一起对比方案时间复杂度空间复杂度评价双指针剥壳O(n)O(1) 额外空间推荐代码短依赖排列性质multiset 模拟O(nlogn)O(n)能过但笨重掩盖题目核心枚举 RMQO(n²)O(nlogn)完全不可行如果这是一道面试题面试官大概率希望听到双指针思路如果这是一场比赛O(nlogn) 的代码在时限内通常也能过但写起来远不如 O(n) 方案爽快。5. 常见问题与排查技巧实录5.1 一直输出 -1先检查这三个位置我帮别人调这题时输出 -1 的情况九成出在三个位置。第一循环条件写成了 lr第二检查完左端之后没有继续循环检查右端导致右端已经变成极值却没被移掉第三low/high 更新和指针移动不配套比如左端点等于 low 时只写了 l忘了 low下一轮判断就用错了最小值。自查方法很简单写一个暴力函数枚举所有区间直接判断然后用随机小数据对拍。暴力程序是绝对参照双指针程序只要输出了一对合法 l、r就说明那次运行没问题。对拍脚本可以用 Python 生成随机排列分别跑暴力程序和双指针程序然后写一个校验函数检查输出的 l、r 是否真的满足“两个端点都不是区间最值”。注意不要比对“两个程序输出是否相同”因为输出任意合法答案都算对。症状常见原因修改方向一直输出 -1循环条件写成 lr改成 while(lr)漏移右端点if-else 链只跑了一遍用 while 反复检查四个条件判断结果全乱low/high 忘记同步更新改成 l,low 的紧凑形式5.2 能不能用 set/线段树维护区间最值可以用但我强烈不建议作为首选。用 multiset 的思路是初始把所有元素放进去set 里的最小值和最大值分别对应 low 和 high移动端点时把对应元素从 set 里删掉再判断端点是否是极值。它能过但每轮删除和插入都是 O(logn)而且判断逻辑并没有变简单。最麻烦的是它不会让你理解“删除 low 之后新最小值必然是 low1”这种排列特性。如果题目改成允许重复的普通数组双指针剥壳会直接失效因为“删除 low 之后新最小值必然是 low1”这句话不再成立。这时候 multiset 也未必能救你因为端点等于当前最小值不代表它不能成为合法端点区间里可能还有另一个相同的最小值判断条件必须改成“端点值等于区间内出现的最小值且没有第二个相同值”之类的复杂表达。所以这题对排列条件的依赖是本质性的不是实现细节。5.3 搜索这个题时的串场热词避坑说实话每次有人第一次做这道题去搜索引擎敲“Dora and Search”第一页大概率混着 docker search redis 报 500 错误、MeiliSearch 在宝塔里怎么配、Windows 搜索组件目录、Bing 的 search host 丢失、同人作品镜像站搜索页还有信息学奥赛一本通里那个叫 keywords search 的题。我最早也被坑过一次翻了好几页才意识到自己该搜的是 Codeforces 题解。避免串场有个小技巧搜索关键词里固定带 Codeforces 四个字母比如直接搜“Dora and Search Codeforces”或者把界面切成英文直接看英文题解原文。中文社区里这题的题解也不少但偶尔有人把相近的几场 Div.2 C 题搞混代码注释可能对不上。一切以你自己跑测试数据的结果为准不要盲目复制。5.4 从这题带走的三个通用经验最后说点我做完这题之后沉淀下来的东西。第一见到排列题先在草稿纸上问自己三句话1 在哪儿n 在哪儿能不能从两端把最值剥掉。很多排列题的关键都藏在这三个问题里。第二双指针并不是只有“滑窗维护合法区间”这一种形态它也可以是“从两端向内排除非法答案”这道题就是后者。第三写题解时把证明写清楚比背代码重要得多。后来我给学弟讲这题只要把“答案区间永远不可能被误删”这句话讲明白对方立刻就懂了。如果你还想继续练同类型的双指针题去找那些“从两端收缩维护值域”的 CF 题目就行换层皮思路还是这一套。多练几道之后再看到“端点与最值”这种条件你的第一反应就不会是线段树而是先想能不能双指针。