求解)
先讲个真实赛时经历。某次线上算法赛做到 C. Dora and Search 这道题时我拿着草稿纸盯了十分钟第一反应是去枚举各种形状的子数组试图手动拼出一个两端都避开了极大值和极小值的区间。结果第一版 (O(n^2)) 的暴力直接在超时边缘摩擦交了被卡卡完我才把思路整个翻转过来——这题真正考的不是“怎么找合法段”而是“怎么快速淘汰不合法的端点”。这篇就完整复盘一下这个思考过程给同样被构造题困住的读者一条可以直接照抄的解题路径。1. 题面在说什么先看懂“两端禁止极值”这个条件1.1 排列输入与子数组定义先交代题面的基本信息。输入一个整数 (n) 和一个长度为 (n) 的排列 (p)所谓排列就是 1 到 (n) 这 (n) 个整数各出现一次不会有重复值。这是本题最重要的背景因为所有极值的唯一性都建立在“不会重复”上最大值只有一个最小值也只有一个任何一个值一旦被排除出区间它就不会再回来捣乱。很多选手在这题上栽跟头其实就是没有利用好排列的这条性质把题目当成普通数组去做。接下来是严格定义求一对下标 (l, r)(1 \le l \le r \le n)使得区间 ([l,r]) 满足两个条件(\max(p_l, p_{l1}, ..., p_r)) 不等于 (p_l)也不等于 (p_r)(\min(p_l, p_{l1}, ..., p_r)) 不等于 (p_l)也不等于 (p_r)。换句话说子数组内部的最大值和最小值都必须“窝在里面”不能是第一个元素也不能是最后一个元素。题目只要求输出任意一对可行 (l, r)不存在就输出 -1。这里有个容易被忽略的点——它不要求区间最短也不要求字典序最小任何合法答案都可以。这直接给了算法很大的自由你完全可以贪心地保留一个较长的区间只要它合法就行。为什么要强调“任意答案即可”因为很多人在做题时会潜意识地去求最短合法区间白白增加复杂度。这道题的正确姿势是找到一个能用的就行不必追求最优。我见过有人把 (l) 从 1 到 (n) 枚举、(r) 也从 (l) 到 (n) 枚举想找最小长度合法段那复杂度直接爆炸。1.2 先手工验证几个合法与非法例子用例子降低理解门槛。第一个例子(p [2, 4, 5, 3, 1])。我们观察整个数组 ([1,5])左端是 2右端是 1。最大值 5 在内部这个没问题但最小值 1 恰好是右端点所以整段不合法。再看子区间 ([2,4])也就是值 ([4,5,3])左端 4、右端 3区间内最大值 5 在内部最小值 3 却在右端又不合法。再看 ([3,4])也就是 ([5,3])长度为 2 的区间天然不合法——两个端点就是全部元素极大值和极小值必定落在这两个位置里。事实上这个数组完全没有合法解。第二个例子(p [3, 1, 4, 2])。取整个数组 ([1,4])左端 3、右端 2区间最大值 4 在内部最小值 1 也在内部完美命中条件。所以答案直接就是 1 4。第三个例子(p [1, 2, 3, 4])单调递增排列。随便取一个子区间 ([l,r])最小值一定在左端 (p_l)最大值一定在右端 (p_r)两端各占一个极值永远不可能合法递减排列同理。这个例子告诉我们单调排列必然无解但要注意无解的排列远不止单调这一种刚才的 ([2,4,5,3,1]) 就不单调但同样无解。2. 从暴搜到洞察为什么思考重心要放在“端点排除”上2.1 直接枚举子数组与极值的复杂度先算一笔账。如果暴力枚举所有 (l, r) 组合区间数量是 (O(n^2))每段再花 (O(区间长度)) 去求最大值和最小值整体是 (O(n^3))。即便优化成枚举 (l) 时滑动 (r)、用数据结构动态维护极值区间的数量本身还是 (O(n^2))在常见的 (n) 达到 (2 \times 10^5) 的数据范围下完全不可接受。这道题显然不是让你把所有区间都看一遍的。那么有没有什么办法把搜索空间压下去观察一个事实任意子数组 ([l,r]) 都可以看成是原数组删掉最左边的若干个元素、再删掉最右边的若干个元素的结果。换句话说从左、从右各删掉一段前缀和后缀剩下的就是你要的区间。既然如此问题的全部可能性并不在“选择一个左端点和一个右端点”的二维平面上而在于“从左删多少、从右删多少”这条一维路径上——如果删多少能被唯一决策复杂度就能做到线性。这正是双指针收缩能奏效的基础合法答案一定可以通过从外向内不断删掉“不可用”的端点来逼近而不是在内部随便裁剪。2.2 把条件翻译成“端点不能站在极值上”接着把合法条件换一种说法当前区间是合法的当且仅当左端点 (p_l) 既不是区间最大值、也不是区间最小值同时右端点 (p_r) 也满足同样的约束。一个端点只要踩在极大值或极小值上这个区间就直接出局反过来只要左右两个端点都“不是极值”区间就一定合法其他内部元素怎么乱都无所谓。这个条件的价值在于它把注意力聚焦到了端点本身是不是极值上。你可以把它理解成一个淘汰游戏站在队伍两端的人如果是最胖或最瘦的那这支队伍就不合格你想要一支合格的队伍只能把不合格的队首或队尾请出去进来的人会不会让队伍变合格就看下一轮的两端表现。由于排列中没有重复值“是当前区间的最大值/最小值”是一个精确且排他的判定不需要考虑平局。这也是为什么这题用双指针做会特别顺端点与极值的比较是 (O(1)) 的而且结论绝对清晰。2.3 排列性质极值随收缩单调变化还有最后一个关键工具排列值域的唯一性。设当前区间 ([l,r]) 是原本整个数组经过若干次删除后剩下的部分那么它的最大值一定是最初的 (n) 中没被删掉的第一个最小值一定是最初的 1 中没被删掉的第一个。更具体地说如果删除的元素是那个最大值 (n)当前最大值立刻变成 (n-1)如果删除的是最小值 1当前最小值立刻变成 2如果删除的是中间某个数值极值一个都不变。这就产生了一条单调变化的规律随着区间收缩当前最小值只会一直变大当前最大值只会一直变小。它让“维护当前区间极值”变成了两次 (O(1)) 的指针步进而不是每次都要重新扫描整个区间。极值从哪里来、往哪里去全部由“被删掉的端点是不是极值”这一个条件决定逻辑非常简单。3. 双指针收缩的完整推导谁被淘汰怎么证明不用回头3.1 收缩规则的形式化描述现在可以直接写出收缩算法。用 (l) 和 (r) 指向当前区间的左右边界用 (mn) 和 (mx) 表示当前区间的最小值和最大值初始为 1 和 (n)。每一轮循环做如下判断如果 (p_l mn)说明当前最小值被左端点占着任何以这个左端点为边界的合法区间都不可能存在所以必须把左端点删掉(l) 加一同时 (mn) 加一否则如果 (p_l mx)同理删掉左端点(l) 加一同时 (mx) 减一否则如果 (p_r mn)右端点占着当前最小值删掉右端点(r) 减一(mn) 加一否则如果 (p_r mx)右端点占着当前最大值删掉右端点(r) 减一(mx) 减一如果四个条件都不成立说明 (p_l) 和 (p_r) 都不是当前区间的极值当前区间已经合法直接输出 (l) 和 (r)。如果循环结束了即 (l r)还没输出说明任何合法区间都不存在输出 -1。需要注意每次循环至多处理一个端点是最稳妥的避免一个端点被重复判断。这里有一个细节当左端点等于 (mn) 被删除后(mn) 增加到 (mn1)而新的左端点 (p_{l1}) 有可能在下一轮刚好等于这个新的 (mn)。这种情况完全正常下一轮循环会再次把它淘汰掉。所以循环的终止条件是“两个端点同时都不踩极值”而不是“左右各检查一次就停”。3.2 为什么收缩是“必须的删减”而不是“碰运气的尝试”需要证明这个贪心算法不会被回溯问题坑到。思路其实是一路排除必然不可行的端点。严格地说如果当前区间 ([l,r]) 的端点 (p_l) 等于当前最小值 (mn)那么我们可以断言在原始数组里任何合法的子数组只要它的左端点是 (l)就一定不合法。原因很简单当前区间 ([l,r]) 已经把所有小于 (mn) 的值排除在外了而 (p_l mn) 又确实在当前区间里所以对任何以 (l) 为左端点的子区间 ([l, R])(p_l) 都是这个子区间内最小值所有比它小的值都不在里面它作为端点踩了极值必然非法。因此合法解的左端点不可能等于 (l)既然连续区间又想避开 (l)那就只能从 (l1) 或更右的位置开始于是我们把左端向内收缩不会漏解。右侧端点踩极值的情况完全对称。这就是“必要排除”的逻辑每一步删除的都是“绝对不可能成为合法解端点”的位置。既然不存在回溯算法自然结束于最早的合法区间或者证明没有合法区间。3.3 两组完整过程演示先演示一个最终无解的数组(p [2, 4, 5, 3, 1])(n 5)。初始(l1, r5, mn1, mx5)。(p_12) 不是极值跳过左检测(p_51) 等于 (mn)于是 (r--)(r4)(mn2)。现在(l1, r4, mn2, mx5)。(p_12) 等于 (mn)于是 (l)(l2)(mn3)。现在(l2, r4, mn3, mx5)。(p_24) 不是极值(p_43) 等于 (mn)于是 (r--)(r3)(mn4)。现在(l2, r3, mn4, mx5)。(p_24) 等于 (mn)于是 (l)(l3)(mn5)。现在(l3, r3)(l r)循环结束输出 -1。再演示一个能找到解的数组(p [1, 3, 5, 2, 4])(n 5)。初始(l1, r5, mn1, mx5)。(p_11) 等于 (mn)删左端(l2)(mn2)。现在(l2, r5, mn2, mx5)。(p_23) 不是极值(p_54) 不是极值。四个条件都不成立输出 2 5。验证区间 ([2,5]) 是 ([3,5,2,4])最小值是 2 在内部下标 4最大值是 5 在内部下标 3端点 3 和 4 都不是极值合法。第二个例子很能说明问题我们只删除了一个全局最小值发现剩下的区间已经满足条件算法立刻收工。如果当初想着把所有端点都检查得干干净净反而浪费时间。4. 边界情况与实现细节真正决定 AC 还是 WA 的几件事4.1 数组长度很小的时候直接判断减少脑内负担(n 1) 时只有一个元素子数组端点既是最大值又是最小值必然非法。(n 2) 同理任何长度为 1 或 2 的子数组端点集要么包含唯一元素要么包含两个恰好是极大极小值的元素都不合法。(n 3) 稍微隐蔽一点长度为 3 的区间只有一个两端各占一个值如果中间值不是极值那极值就必然落在两端如果中间值是极值那么至少有一端踩极值总之不可能合法。所以 (n \le 3) 时可以直接输出 -1。很多新手没意识到 (n3) 也直接无解会浪费时间挣扎。更值得警惕的是 (n4) 或 (n5) 时也有许多无解排列比如刚才的 ([2,4,5,3,1])。这意味着如果你对样例数据做局部修改想要凑一个答案很容易被误导。对付这些情况最好的办法不是手推而是直接让算法跑一遍收缩过程看它最终是否停在 (l r)。4.2 循环终止条件的三种实现与一个常见误区我在赛时一共试过三种写法最终只推荐一种。第一种写法是每次循环把左右端点都“试着处理一遍”用 if 判断四个条件若四个都不满足就输出。这种写法的问题在于如果左右端点恰好都踩极值一次迭代只删一个端点没问题但如果删完左端点导致 (mn/mx) 更新新的极值可能正好落在右端点上此时下一次循环还要重新检查右端点逻辑上没错但可读性差点。第二种写法是内层 while 循环分别把左右端点处理到“安全”为止但要注意先处理完左端点后右端点检测使用的 (mn/mx) 可能已经变化需要重新处理左端点吗不太需要因为新的左端点是固定值它不可能因为右端删除极值而“变成”新的极值除非它恰好等于新极值这是可能发生的。所以一次性把某侧处理干净并不安全。我推荐第三种最朴素的写法外层while (l r)每次循环体里从上到下按左最小、左最大、右最小、右最大的顺序判断是就删一个并更新然后进入下一轮四个都不是才 break 输出。伪代码如下l 1 r n mn 1 mx n ok false while l r: if p[l] mn: l 1 mn 1 else if p[l] mx: l 1 mx - 1 else if p[r] mn: r - 1 mn 1 else if p[r] mx: r - 1 mx - 1 else: ok true break if ok: print(l, r) else: print(-1)每次循环只处理一个端点逻辑简单并且不会漏掉“一侧处理完导致另一侧新极值出现”的情况下一轮自然检测。还有人会担心while (l r)会不会在某一步之后 (l r) 但还存在合法长度为 1 的区间不会长度为 1 的区间不可能合法所以循环条件完全没问题。4.3 同步更新 mn 和 mx唯一会让你 WA 的“小地方”真正容易出错的环节是 (mn) 和 (mx) 的更新时机。切记只有当被删除的端点恰好等于当前 (mn) 时最小值才递增只有当它恰好等于当前 (mx) 时最大值才递减删除普通中间值时两个极值都保持不变。如果把“端点等于极值”和“更新极值”绑定在一起写代码最不容易乱。举个例子当前区间 ([1,4])(mn1)(mx5)右端点 (p_43)。此时右端点既不是 (mn) 也不是 (mx)删除它之后新区间 ([1,3]) 的极值依然是 1 和 5因为值 3 本来就是夹在中间的元素。如果代码里不论删除什么值都执行 (mn) 或 (mx--)正确性立刻崩塌。我还见过一种错误删除左端点后把 (mn) 更新成min(mn1, p[l])之类的“保险操作”。完全没必要反而制造混乱。因为 (p_l) 的值不可能小于 (mn)所有更小值都被删掉了也不可能大于 (mx)极值的走向是确定的加一减一就好不需要额外取 min/max。5. 从这道题沉淀下来的通用套路与实测心得5.1 复杂度分析与为什么能做到线性算法每个周期要么让 (l) 右移要么让 (r) 左移每个下标最多被处理一次所以总时间复杂度是 (O(n))。额外空间只需要常量几个变量(O(1))。在排列题里这几乎是零开销级别的优雅解法。能够做到线性本质上是因为我们找到了一个“单调排除”的结构每次删除都是基于必要条件的删掉的东西绝不可能在答案里。一旦你知道哪些位置必然不在答案端点中搜索就从 (O(n^2)) 的平面问题退化成 (O(n)) 的路径问题。这种“先证必要性再让必要性推动决策”的思维比任何高级数据结构都管用。当 (n) 特别大比如 (2 \times 10^5)、序列又是随机排列时这个算法基本在几毫秒内跑完。但要注意一点输入输出一定要用快速 IO 方案否则这种排列题最容易在 IO 上翻车算法本身再快也白搭。5.2 从这道题总结的“端点排除法”能迁移到哪里这道题背后是一个可迁移的思考模式当问题要求某个区间或子序列满足与极值相关的条件时优先看当前区间的两端能不能提供任何“否决票”。具体有三个层次第一如果端点本身是极值那么这个端点所在的任何答案都不成立只能排除第二排除极值端点后区间缩小极值集合也随之缩小形成自然的迭代结构第三由于排列中每个值唯一排除与否的判断可以做到 (O(1))。这套模式在很多极值类题目里出现过比如“删除最小次数让剩余数组满足条件”“两端取数的博弈”等虽然形式不同但审视端点的思路是一致的。另外这道题还提供了一个反直觉的结论很多看起来无解的排列并不是单调排列。所以做题时不要靠“单调就无解非单调就有解”这样的伪结论偷懒务必回到算法本身去验证。5.3 赛时复盘与个人经验最后说一点个人经验。我第一次做这道题时被“构造”两个字骗住了一直在想如何从全局最大值和最小值的位置出发手动设计答案区间。其实题目的数据范围已经暗示了这不是构造题而是判定加双指针题。我的建议是拿到这种题先做三件事一把合法条件用自然语言重写一遍直到能脱口而出“端点不允许是极值”二找一个无解的小数组手动跑一遍排除过程理解为什么每次都只能删端点三敲代码前先想清楚 (mn/mx) 的更新机制再动手。做完这三步这道题基本不会写错。如果再给我一次机会我会在草稿纸上先写一个随机排列如 ([1,3,5,2,4])然后逐轮收缩用笔模拟出“删一次就找到答案”的过程而不是直接空想算法。模拟一个具体例子的时间往往比纠结十分钟伪代码更值得。这题对我最大的启发是能删除的才删不能删除的默认保留答案往往就在“最小必要删除”处等着你。遇到过不去的问题时先别急着找构造试着问自己哪些位置必须被排除 
长河君 · 2026/10/10 11:01:06 · 阅读 1.2k 排列子数组两端禁极值？双指针端点排除法O(n)求解
先讲个真实赛时经历。某次线上算法赛做到 C. Dora and Search 这道题时我拿着草稿纸盯了十分钟第一反应是去枚举各种形状的子数组试图手动拼出一个两端都避开了极大值和极小值的区间。结果第一版 (O(n^2)) 的暴力直接在超时边缘摩擦交了被卡卡完我才把思路整个翻转过来——这题真正考的不是“怎么找合法段”而是“怎么快速淘汰不合法的端点”。这篇就完整复盘一下这个思考过程给同样被构造题困住的读者一条可以直接照抄的解题路径。1. 题面在说什么先看懂“两端禁止极值”这个条件1.1 排列输入与子数组定义先交代题面的基本信息。输入一个整数 (n) 和一个长度为 (n) 的排列 (p)所谓排列就是 1 到 (n) 这 (n) 个整数各出现一次不会有重复值。这是本题最重要的背景因为所有极值的唯一性都建立在“不会重复”上最大值只有一个最小值也只有一个任何一个值一旦被排除出区间它就不会再回来捣乱。很多选手在这题上栽跟头其实就是没有利用好排列的这条性质把题目当成普通数组去做。接下来是严格定义求一对下标 (l, r)(1 \le l \le r \le n)使得区间 ([l,r]) 满足两个条件(\max(p_l, p_{l1}, ..., p_r)) 不等于 (p_l)也不等于 (p_r)(\min(p_l, p_{l1}, ..., p_r)) 不等于 (p_l)也不等于 (p_r)。换句话说子数组内部的最大值和最小值都必须“窝在里面”不能是第一个元素也不能是最后一个元素。题目只要求输出任意一对可行 (l, r)不存在就输出 -1。这里有个容易被忽略的点——它不要求区间最短也不要求字典序最小任何合法答案都可以。这直接给了算法很大的自由你完全可以贪心地保留一个较长的区间只要它合法就行。为什么要强调“任意答案即可”因为很多人在做题时会潜意识地去求最短合法区间白白增加复杂度。这道题的正确姿势是找到一个能用的就行不必追求最优。我见过有人把 (l) 从 1 到 (n) 枚举、(r) 也从 (l) 到 (n) 枚举想找最小长度合法段那复杂度直接爆炸。1.2 先手工验证几个合法与非法例子用例子降低理解门槛。第一个例子(p [2, 4, 5, 3, 1])。我们观察整个数组 ([1,5])左端是 2右端是 1。最大值 5 在内部这个没问题但最小值 1 恰好是右端点所以整段不合法。再看子区间 ([2,4])也就是值 ([4,5,3])左端 4、右端 3区间内最大值 5 在内部最小值 3 却在右端又不合法。再看 ([3,4])也就是 ([5,3])长度为 2 的区间天然不合法——两个端点就是全部元素极大值和极小值必定落在这两个位置里。事实上这个数组完全没有合法解。第二个例子(p [3, 1, 4, 2])。取整个数组 ([1,4])左端 3、右端 2区间最大值 4 在内部最小值 1 也在内部完美命中条件。所以答案直接就是 1 4。第三个例子(p [1, 2, 3, 4])单调递增排列。随便取一个子区间 ([l,r])最小值一定在左端 (p_l)最大值一定在右端 (p_r)两端各占一个极值永远不可能合法递减排列同理。这个例子告诉我们单调排列必然无解但要注意无解的排列远不止单调这一种刚才的 ([2,4,5,3,1]) 就不单调但同样无解。2. 从暴搜到洞察为什么思考重心要放在“端点排除”上2.1 直接枚举子数组与极值的复杂度先算一笔账。如果暴力枚举所有 (l, r) 组合区间数量是 (O(n^2))每段再花 (O(区间长度)) 去求最大值和最小值整体是 (O(n^3))。即便优化成枚举 (l) 时滑动 (r)、用数据结构动态维护极值区间的数量本身还是 (O(n^2))在常见的 (n) 达到 (2 \times 10^5) 的数据范围下完全不可接受。这道题显然不是让你把所有区间都看一遍的。那么有没有什么办法把搜索空间压下去观察一个事实任意子数组 ([l,r]) 都可以看成是原数组删掉最左边的若干个元素、再删掉最右边的若干个元素的结果。换句话说从左、从右各删掉一段前缀和后缀剩下的就是你要的区间。既然如此问题的全部可能性并不在“选择一个左端点和一个右端点”的二维平面上而在于“从左删多少、从右删多少”这条一维路径上——如果删多少能被唯一决策复杂度就能做到线性。这正是双指针收缩能奏效的基础合法答案一定可以通过从外向内不断删掉“不可用”的端点来逼近而不是在内部随便裁剪。2.2 把条件翻译成“端点不能站在极值上”接着把合法条件换一种说法当前区间是合法的当且仅当左端点 (p_l) 既不是区间最大值、也不是区间最小值同时右端点 (p_r) 也满足同样的约束。一个端点只要踩在极大值或极小值上这个区间就直接出局反过来只要左右两个端点都“不是极值”区间就一定合法其他内部元素怎么乱都无所谓。这个条件的价值在于它把注意力聚焦到了端点本身是不是极值上。你可以把它理解成一个淘汰游戏站在队伍两端的人如果是最胖或最瘦的那这支队伍就不合格你想要一支合格的队伍只能把不合格的队首或队尾请出去进来的人会不会让队伍变合格就看下一轮的两端表现。由于排列中没有重复值“是当前区间的最大值/最小值”是一个精确且排他的判定不需要考虑平局。这也是为什么这题用双指针做会特别顺端点与极值的比较是 (O(1)) 的而且结论绝对清晰。2.3 排列性质极值随收缩单调变化还有最后一个关键工具排列值域的唯一性。设当前区间 ([l,r]) 是原本整个数组经过若干次删除后剩下的部分那么它的最大值一定是最初的 (n) 中没被删掉的第一个最小值一定是最初的 1 中没被删掉的第一个。更具体地说如果删除的元素是那个最大值 (n)当前最大值立刻变成 (n-1)如果删除的是最小值 1当前最小值立刻变成 2如果删除的是中间某个数值极值一个都不变。这就产生了一条单调变化的规律随着区间收缩当前最小值只会一直变大当前最大值只会一直变小。它让“维护当前区间极值”变成了两次 (O(1)) 的指针步进而不是每次都要重新扫描整个区间。极值从哪里来、往哪里去全部由“被删掉的端点是不是极值”这一个条件决定逻辑非常简单。3. 双指针收缩的完整推导谁被淘汰怎么证明不用回头3.1 收缩规则的形式化描述现在可以直接写出收缩算法。用 (l) 和 (r) 指向当前区间的左右边界用 (mn) 和 (mx) 表示当前区间的最小值和最大值初始为 1 和 (n)。每一轮循环做如下判断如果 (p_l mn)说明当前最小值被左端点占着任何以这个左端点为边界的合法区间都不可能存在所以必须把左端点删掉(l) 加一同时 (mn) 加一否则如果 (p_l mx)同理删掉左端点(l) 加一同时 (mx) 减一否则如果 (p_r mn)右端点占着当前最小值删掉右端点(r) 减一(mn) 加一否则如果 (p_r mx)右端点占着当前最大值删掉右端点(r) 减一(mx) 减一如果四个条件都不成立说明 (p_l) 和 (p_r) 都不是当前区间的极值当前区间已经合法直接输出 (l) 和 (r)。如果循环结束了即 (l r)还没输出说明任何合法区间都不存在输出 -1。需要注意每次循环至多处理一个端点是最稳妥的避免一个端点被重复判断。这里有一个细节当左端点等于 (mn) 被删除后(mn) 增加到 (mn1)而新的左端点 (p_{l1}) 有可能在下一轮刚好等于这个新的 (mn)。这种情况完全正常下一轮循环会再次把它淘汰掉。所以循环的终止条件是“两个端点同时都不踩极值”而不是“左右各检查一次就停”。3.2 为什么收缩是“必须的删减”而不是“碰运气的尝试”需要证明这个贪心算法不会被回溯问题坑到。思路其实是一路排除必然不可行的端点。严格地说如果当前区间 ([l,r]) 的端点 (p_l) 等于当前最小值 (mn)那么我们可以断言在原始数组里任何合法的子数组只要它的左端点是 (l)就一定不合法。原因很简单当前区间 ([l,r]) 已经把所有小于 (mn) 的值排除在外了而 (p_l mn) 又确实在当前区间里所以对任何以 (l) 为左端点的子区间 ([l, R])(p_l) 都是这个子区间内最小值所有比它小的值都不在里面它作为端点踩了极值必然非法。因此合法解的左端点不可能等于 (l)既然连续区间又想避开 (l)那就只能从 (l1) 或更右的位置开始于是我们把左端向内收缩不会漏解。右侧端点踩极值的情况完全对称。这就是“必要排除”的逻辑每一步删除的都是“绝对不可能成为合法解端点”的位置。既然不存在回溯算法自然结束于最早的合法区间或者证明没有合法区间。3.3 两组完整过程演示先演示一个最终无解的数组(p [2, 4, 5, 3, 1])(n 5)。初始(l1, r5, mn1, mx5)。(p_12) 不是极值跳过左检测(p_51) 等于 (mn)于是 (r--)(r4)(mn2)。现在(l1, r4, mn2, mx5)。(p_12) 等于 (mn)于是 (l)(l2)(mn3)。现在(l2, r4, mn3, mx5)。(p_24) 不是极值(p_43) 等于 (mn)于是 (r--)(r3)(mn4)。现在(l2, r3, mn4, mx5)。(p_24) 等于 (mn)于是 (l)(l3)(mn5)。现在(l3, r3)(l r)循环结束输出 -1。再演示一个能找到解的数组(p [1, 3, 5, 2, 4])(n 5)。初始(l1, r5, mn1, mx5)。(p_11) 等于 (mn)删左端(l2)(mn2)。现在(l2, r5, mn2, mx5)。(p_23) 不是极值(p_54) 不是极值。四个条件都不成立输出 2 5。验证区间 ([2,5]) 是 ([3,5,2,4])最小值是 2 在内部下标 4最大值是 5 在内部下标 3端点 3 和 4 都不是极值合法。第二个例子很能说明问题我们只删除了一个全局最小值发现剩下的区间已经满足条件算法立刻收工。如果当初想着把所有端点都检查得干干净净反而浪费时间。4. 边界情况与实现细节真正决定 AC 还是 WA 的几件事4.1 数组长度很小的时候直接判断减少脑内负担(n 1) 时只有一个元素子数组端点既是最大值又是最小值必然非法。(n 2) 同理任何长度为 1 或 2 的子数组端点集要么包含唯一元素要么包含两个恰好是极大极小值的元素都不合法。(n 3) 稍微隐蔽一点长度为 3 的区间只有一个两端各占一个值如果中间值不是极值那极值就必然落在两端如果中间值是极值那么至少有一端踩极值总之不可能合法。所以 (n \le 3) 时可以直接输出 -1。很多新手没意识到 (n3) 也直接无解会浪费时间挣扎。更值得警惕的是 (n4) 或 (n5) 时也有许多无解排列比如刚才的 ([2,4,5,3,1])。这意味着如果你对样例数据做局部修改想要凑一个答案很容易被误导。对付这些情况最好的办法不是手推而是直接让算法跑一遍收缩过程看它最终是否停在 (l r)。4.2 循环终止条件的三种实现与一个常见误区我在赛时一共试过三种写法最终只推荐一种。第一种写法是每次循环把左右端点都“试着处理一遍”用 if 判断四个条件若四个都不满足就输出。这种写法的问题在于如果左右端点恰好都踩极值一次迭代只删一个端点没问题但如果删完左端点导致 (mn/mx) 更新新的极值可能正好落在右端点上此时下一次循环还要重新检查右端点逻辑上没错但可读性差点。第二种写法是内层 while 循环分别把左右端点处理到“安全”为止但要注意先处理完左端点后右端点检测使用的 (mn/mx) 可能已经变化需要重新处理左端点吗不太需要因为新的左端点是固定值它不可能因为右端删除极值而“变成”新的极值除非它恰好等于新极值这是可能发生的。所以一次性把某侧处理干净并不安全。我推荐第三种最朴素的写法外层while (l r)每次循环体里从上到下按左最小、左最大、右最小、右最大的顺序判断是就删一个并更新然后进入下一轮四个都不是才 break 输出。伪代码如下l 1 r n mn 1 mx n ok false while l r: if p[l] mn: l 1 mn 1 else if p[l] mx: l 1 mx - 1 else if p[r] mn: r - 1 mn 1 else if p[r] mx: r - 1 mx - 1 else: ok true break if ok: print(l, r) else: print(-1)每次循环只处理一个端点逻辑简单并且不会漏掉“一侧处理完导致另一侧新极值出现”的情况下一轮自然检测。还有人会担心while (l r)会不会在某一步之后 (l r) 但还存在合法长度为 1 的区间不会长度为 1 的区间不可能合法所以循环条件完全没问题。4.3 同步更新 mn 和 mx唯一会让你 WA 的“小地方”真正容易出错的环节是 (mn) 和 (mx) 的更新时机。切记只有当被删除的端点恰好等于当前 (mn) 时最小值才递增只有当它恰好等于当前 (mx) 时最大值才递减删除普通中间值时两个极值都保持不变。如果把“端点等于极值”和“更新极值”绑定在一起写代码最不容易乱。举个例子当前区间 ([1,4])(mn1)(mx5)右端点 (p_43)。此时右端点既不是 (mn) 也不是 (mx)删除它之后新区间 ([1,3]) 的极值依然是 1 和 5因为值 3 本来就是夹在中间的元素。如果代码里不论删除什么值都执行 (mn) 或 (mx--)正确性立刻崩塌。我还见过一种错误删除左端点后把 (mn) 更新成min(mn1, p[l])之类的“保险操作”。完全没必要反而制造混乱。因为 (p_l) 的值不可能小于 (mn)所有更小值都被删掉了也不可能大于 (mx)极值的走向是确定的加一减一就好不需要额外取 min/max。5. 从这道题沉淀下来的通用套路与实测心得5.1 复杂度分析与为什么能做到线性算法每个周期要么让 (l) 右移要么让 (r) 左移每个下标最多被处理一次所以总时间复杂度是 (O(n))。额外空间只需要常量几个变量(O(1))。在排列题里这几乎是零开销级别的优雅解法。能够做到线性本质上是因为我们找到了一个“单调排除”的结构每次删除都是基于必要条件的删掉的东西绝不可能在答案里。一旦你知道哪些位置必然不在答案端点中搜索就从 (O(n^2)) 的平面问题退化成 (O(n)) 的路径问题。这种“先证必要性再让必要性推动决策”的思维比任何高级数据结构都管用。当 (n) 特别大比如 (2 \times 10^5)、序列又是随机排列时这个算法基本在几毫秒内跑完。但要注意一点输入输出一定要用快速 IO 方案否则这种排列题最容易在 IO 上翻车算法本身再快也白搭。5.2 从这道题总结的“端点排除法”能迁移到哪里这道题背后是一个可迁移的思考模式当问题要求某个区间或子序列满足与极值相关的条件时优先看当前区间的两端能不能提供任何“否决票”。具体有三个层次第一如果端点本身是极值那么这个端点所在的任何答案都不成立只能排除第二排除极值端点后区间缩小极值集合也随之缩小形成自然的迭代结构第三由于排列中每个值唯一排除与否的判断可以做到 (O(1))。这套模式在很多极值类题目里出现过比如“删除最小次数让剩余数组满足条件”“两端取数的博弈”等虽然形式不同但审视端点的思路是一致的。另外这道题还提供了一个反直觉的结论很多看起来无解的排列并不是单调排列。所以做题时不要靠“单调就无解非单调就有解”这样的伪结论偷懒务必回到算法本身去验证。5.3 赛时复盘与个人经验最后说一点个人经验。我第一次做这道题时被“构造”两个字骗住了一直在想如何从全局最大值和最小值的位置出发手动设计答案区间。其实题目的数据范围已经暗示了这不是构造题而是判定加双指针题。我的建议是拿到这种题先做三件事一把合法条件用自然语言重写一遍直到能脱口而出“端点不允许是极值”二找一个无解的小数组手动跑一遍排除过程理解为什么每次都只能删端点三敲代码前先想清楚 (mn/mx) 的更新机制再动手。做完这三步这道题基本不会写错。如果再给我一次机会我会在草稿纸上先写一个随机排列如 ([1,3,5,2,4])然后逐轮收缩用笔模拟出“删一次就找到答案”的过程而不是直接空想算法。模拟一个具体例子的时间往往比纠结十分钟伪代码更值得。这题对我最大的启发是能删除的才删不能删除的默认保留答案往往就在“最小必要删除”处等着你。遇到过不去的问题时先别急着找构造试着问自己哪些位置必须被排除