牛客周赛127我赛时卡在B题上将近二十分钟说出去有点丢人但复盘之后我觉得这二十分钟花得值——这题的套路绝对不只适用于牛客这一场。题面核心就一句话给一个数组每次可以把一个长度为3的连续子串反转问能不能让整个数组变成有序。听上去像模拟题实际上只要看穿“反转长度3”这个操作的本质十行代码就能解决。这篇复盘我把完整的推导过程、代码实现和赛时踩的坑都写出来给被B题折腾过的同学也给自己留个存档。1. B题长什么样一个看似暴力能解的陷阱1.1 题面还原与我的第一反应先说题面。按我赛时的记忆版本大概是这样的给定一个长度为 n 的数组 an 的范围在本场大概是几千到十万这个量级元素可能有重复。允许的操作只有一种——选择一个长度为 3 的连续子数组原地反转它的顺序也就是[x, y, z]变成[z, y, x]。操作可以执行任意多次每次可以作用于任意位置。问最终能否把整个数组变成非递减顺序也就是排序后的样子。我第一反应是这不就是不断交换相邻元素吗因为反转长度3不就是把两边的元素互换一下那是否存在一个类似“冒泡排序”的构造只要我找到合适的交换序列就能排好顺着这个思路我甚至考虑过用 BFS 搜索状态空间但很快就否了——n 稍微大一点状态数根本没法枚举。而且题目问的是“能否”不是“最少几步”这通常意味着背后存在一个判定条件一旦想清楚条件代码会非常简单。后来在牛客讨论区逛了一圈发现不少人和我一样卡在“把反转拆解成若干相邻交换”的惯性思维里。还有人提到这题和 LeetCode 周赛430里某道题的套路很像都是“距离为2的交换”。当时没细看但核心思想确实是一致的操作影响的范围决定了哪些元素可以互换哪些元素永远隔着一道墙。1.2 为什么暴力模拟和贪心都不靠谱有人可能会说我直接从头到尾扫描遇到逆序就就地反转一次不行吗这题的危险之处就在这里贪心很容易给你一个“差不多对”的错觉。举个例子数组是[3, 2, 1]你看到3 2反转前三个得到[1, 2, 3]恰好成功。但数组是[5, 1, 4, 2, 3]呢从头贪心反转很可能陷入局部调整最后却差那么一个元素排不进去。因为长度3的反转不是任意交换它每次固定的交换位置是i和i2中间那个位置反而不动。如果你没有意识到这个约束就会高估自己的操控能力。并且操作次数理论上无限搜索和贪心都依赖“最优解”的概念而这题根本没有步数限制只需要一个存在性判定。所以正确的打开方式不是模拟操作过程而是分析操作本身的代数性质找出它不改变什么。这就像玩魔方你不需要真的去转几百步先搞清楚哪些色块永远只能待在哪些面上问题往往瞬间就瓦解了。2. 长度3反转的数学本质隔位交换2.1 手动实验把反转等价写成交换先把操作抽象出来。对下标i, i1, i2三个位置原来的值是[a, b, c]反转后是[c, b, a]。比较一下就能发现位置i的值变成了原来的c等于位置i2的值位置i2的值变成了原来的a等于位置i的值位置i1的值还是原来的b根本没有变化。所以“反转长度3的连续子串”在数学上就是一句话交换下标相差2的两个位置上的元素中间那个元素纹丝不动。这不是近似而是严格的等价关系。以后看到形如“反转子数组”的操作先别急着套全区间反转的模板先看长度长度是3、是4、是5结论完全不同。我把这个观察写下来之后脑子里立刻蹦出一个图像整个数组的下标被染成两种颜色偶数下标一类奇数下标一类。一次操作交换的是同色格子里的两个元素永远不会让一个元素从偶数字格跳到奇数字格里。这意味着阵列被分成了两个独立的“抽屉”操作只能在抽屉内部搬东西。2.2 不变量奇偶下标分组不可跨越这个“不变量”是整个题目的灵魂。无论你怎么操作或者操作多少次下面两个事实始终成立原来在偶数下标上的元素未来一定还在某个偶数下标上原来在奇数下标上的元素未来一定还在某个奇数下标上。用集合的语言说设E是原数组偶数下标位置的元素集合O是奇数下标位置的元素集合那么任意可达的数组它的偶数下标位置装的一定还是E这个多重集奇数下标位置装的一定还是O这个多重集。元素的值可以变位置但不可以变组别。很多同学看到这里会问那是不是就完事了只要判断原数组和目标数组在偶数位置集合、奇数位置集合上分别相等就能判定可达对这就是题目的骨架。但还有一层需要证明同一个组内部是不是任意排列都能做到毕竟我们只有“交换相距为2的两个元素”这一种操作万一偶数位内部的某些排列永远无法实现呢这就是下一节要解决的问题。3. 可达性判定从“隔位交换”到“分组排序”3.1 三步交换法证明同组内任意两元素可交换为了严谨我需要证明任取两个偶数下标的元素无论它们隔得多远都可以通过若干次长度3的反转完成交换而且不影响其他元素。直接给结论距离为2的两个位置一次反转就能互换距离为4的两个位置三次反转就能互换且其他元素全部复位。拿下标i和i4举例假设四个位置初值是[x, y, z, w, v]其中x在iy在i1z在i2w在i3v在i4目标是交换x和v。第一次反转区间[i, i1, i2]交换x和z序列变成[z, y, x, w, v]第二次反转区间[i2, i3, i4]交换x和v序列变成[z, y, v, w, x]第三次反转区间[i, i1, i2]交换z和v序列变成[v, y, z, w, x]。看最后的结果x去了i4v去了i中间的y、z、w全部回到了原位。这一步很关键它告诉我们隔4位的交换可以干净利落地完成。至于隔6位、隔8位可以用同样的思想逐步“搬运”本质上和冒泡排序里的相邻交换一样同奇偶内部任意排列都能构造出来。所以充分性成立偶数位置元素可以被重排成这组元素对应的任意顺序奇数位置同理。3.2 目标有序数组的唯一候选结构有了上面的结论整个问题就变成了给定两个独立的子序列分别由原数组偶数下标的元素和奇数下标的元素组成要求把它们重新交错放回原来的位置能否构成一个非递减数组注意如果最终要整体非递减那么偶数位置子序列内部必须非递减奇数位置子序列内部也必须非递减。因为两个相邻的偶数下标位置中间夹着一个奇数下标虽然直接看它们不相邻但在整个数组里偶位置序列是交错排列的如果两个偶位置元素e1 e2且e1在e2左边那么无论中间奇数位置的值是多少这个数组都不可能整体非递减。奇数位置同理。因此最终的有序数组即使存在其结构也是被唯一确定的把原数组偶数下标的元素全部取出来排序奇数下标的元素全部取出来排序然后按原来的下标交错拼接。如果拼接出来的数组已经非递减那么答案就是“能”如果这样都不行那换个排列方式只会更乱不存在其他可能的成功方案。这里我多说一句为什么要“分别排序”。有人可能觉得反正元素值一样排不排序无所谓。但数组元素可能有重复而且排序能让我们把“可行性”压缩成一个可检查的确定性数组而不是在一堆排列里大海捞针。对单调性判断来说排序后的组合就是最乐观的情况如果最乐观的情况都无法满足非递减那其他任何排列都满足不了。4. 代码实现核心逻辑其实只有十行4.1 先写可读性最强的Python版本我把判定逻辑写成 Python结构非常清晰def can_make_sorted(a): n len(a) even sorted(a[0::2]) odd sorted(a[1::2]) res [] ei oi 0 for i in range(n): if i % 2 0: res.append(even[ei]) ei 1 else: res.append(odd[oi]) oi 1 return all(res[i] res[i1] for i in range(n-1))a[0::2]取所有偶数下标元素a[1::2]取所有奇数下标元素。排序后交错放回最后判断整个数组是否非递减。复杂度是O(n log n)对十万量级的数据完全够用。如果 n 很小比如小于3这段代码也自动处理了偶数下标元素只有位置0奇数下标元素可能没有或只有位置1排序交错后等于原样判断。4.2 同样的逻辑用 C 实现牛客周赛很多同学习惯用 C 交写法如下#include bits/stdc.h using namespace std; bool canMakeSorted(vectorint a) { int n (int)a.size(); vectorint even, odd; for (int i 0; i n; i) { if (i % 2 0) even.push_back(a[i]); else odd.push_back(a[i]); } sort(even.begin(), even.end()); sort(odd.begin(), odd.end()); vectorint res(n); int ei 0, oi 0; for (int i 0; i n; i) { if (i % 2 0) res[i] even[ei]; else res[i] odd[oi]; } for (int i 0; i 1 n; i) { if (res[i] res[i 1]) return false; } return true; }这里唯一要注意的是几个空指针类的边界odd可能为空比如 n1 时但排序空数组没问题交错循环里oi也不会越界因为奇数下标不存在就不会走到odd[oi]。C 的sort对空 vector 是安全的。4.3 复杂度分析与一个计数特例时间复杂度O(n log n)空间复杂度O(n)。排序是主要开销如果 n 到二十万C 几毫秒就能跑完Python 也完全在可接受范围。不过赛场上我后来发现一个更快的写法。如果题目明确说数组里只有 0 和 101串版本排序判定可以退化成纯计数不需要真的排序。设整个数组里 0 的个数是k目标有序数组应该是前k个位置全是0后面全是1。因为偶位置和奇位置不能互相交换只需要检查原数组偶数下标位置上的0的数量是否等于前k个下标中偶数下标的数量奇数下标上的0的数量是否等于前k个下标中奇数下标的数量。写成公式就是偶数位0的个数必须等于(k 1) // 20-indexed 下前 k 个位置中偶数下标数量奇数位0的个数必须等于k // 2。这个特例在很多类似题里会出现遇到01串别傻傻排序两行统计就过去了。5. 赛时踩坑与边界用例复盘5.1 第一次WA我只排序了偶数组赛时我的第一版代码只对偶位置子序列排了序奇数位置保持原样就直接判断了。结果当然WA。原因很直白奇数位置内部也是可以自由重排的我忽略了这一半的操控能力。举个例子数组[3, 1, 2]偶位置是3, 2排序后变成[2, 1, 3]判断互相比较发现不有序就返回 false。但如果把奇数位置1也考虑进去奇数位置只有一个元素排列不变结果仍然是[2, 1, 3]所以这个例子的确应该是 false。换成[3, 2, 1]呢偶位置3, 1排序后是[1, 2]奇数位置2不动得到[1, 2, 3]成功。这里的关键是两边都要参与重排漏掉任何一边都会造成误判。5.2 第二次WA忘记检查整体非递减第二版我把两边都排序了但没有做“交错放回”这个动作而是直接把排序后的偶数组、奇数组拼接成一个新数组去判断。这等于改变了元素在整体数组中的位置结构。比如原数组长度6偶数组有三个数、奇数组有三个数我把它们拼接成“前三个是偶数组后三个是奇数组”这和实际交错排列完全不是一回事。正确做法必须按照原下标 0、1、2、3... 逐个填充先放偶数组第一个再放奇数组第一个再放偶数组第二个以此类推。这一步提醒我这类题的“重排”不是整体重排而是保持固定插槽位置的局部重排。5.3 边界用例与重复元素问题再说几个容易翻车的边界情况。数组长度 n1 或 n2 时根本不存在长度为3的连续子串一次操作都做不了所以只能判断原数组是否有序。我的代码天然覆盖排序空数组后交错放回结果就是原数组判断逻辑自动生效。重复元素也很容易出问题。比如[2, 2, 1, 1, 2, 2]偶位置元素集合是{2, 1, 2}排序后[1, 2, 2]奇位置元素集合是{2, 1, 2}排序后[1, 2, 2]。交错得到[1, 1, 2, 2, 2, 2]有序答案是 true。这里排序是有序数组的构造过程重复元素不需要特殊处理只要你把所有同值元素当成无差别个体看待就行。问题的关键是防止自己把重复元素用于区分奇偶分组——哪怕两个值相同的元素一个在偶组、一个在奇组它们仍然不能互换位置因为值相同可以掩盖位置差异但这个差异对“能否构造”没有影响所以不用区分。5.4 比赛群里的联想LeetCode周赛430的近似套路赛后看讨论有人提到这题的“隔位交换”和 LeetCode 周赛430的某道题思路很像。我没有去细翻那道题的题号但可以确认的是这种“限制操作距离固定”的题型在各大周赛里出现频率极高。套路一般是三步走分析单次操作等价于哪些位置交换提炼出不可跨越的分组对每个分组独立处理后判断整个结构是否满足目标性质。能迁移这个框架比背一道题有用得多。6. 通用套路总结子串操作先找不变量6.1 如何快速识别这类题以后再遇到“每次操作可选一个子数组做XXX反转/旋转/位移问能否变成目标序列”我的建议是别急着写模拟先做两件事。第一把单次操作写成最细粒度的等价形式。比如“反转长度3”展开为“交换位置i和i2”“反转长度4”可能是“交换i和i3、i1和i2”的组合长度不同结论会有巨大差异。第二找出操作无法跨越的“墙”。只要元素被分成两个或多个互不流通的组题目就从“全排列搜索”降维成“分组判定”。这种思路在 Git 仓库里有个很形象的类比两个分支之间不允许 merge只能在各自分支内部乱序提交然后问最终整个仓库的文件版本序列能不能排成某个顺序。答案就是看两个分支的内部内容是否和期望序列匹配。6.2 变式迁移如果操作是反转长度4把这套方法迁移到变式上比如“每次反转长度为4的连续子数组”。单次反转[a,b,c,d]得到[d,c,b,a]等价于两对交换a和d互换b和c互换。第一对是下标差3奇偶性不同第二对是下标差1奇偶性也不同。这就有意思了——它不是隔位交换而是“交界交换”可能所有元素全部打通也可能形成另外一个分组结构。处理方式依然是先写出等价交换对再分析这些交换对构成的图上的连通分量同一连通分量的元素可以任意互换判定就转化为各连通分量的元素集合比较。我不展开完整推导但方法框架是一致的。6.3 最后分享一个实操小技巧我个人习惯在写这类题之前先在草稿纸上列一个极小的例子比如 n5手动把一次操作的前后状态写出来标出哪些下标发生了元素移动。这个动作只需要三十秒却常常能直接看出分组。很多同学直接上代码最后被样例卡住才回来推规律反而更浪费时间。赛场上时间紧更要先动笔后写码。这题的收获对我来说不只是 AC 本身更是一种提醒操作类题目中的“操作”往往不是给你模拟用的而是给你分析用的。抓住不变量复杂的数据流动瞬间就变得清楚。下次在牛客周赛再碰到“连续子串”相关的操作题我大概能更快地找到那条通往结论的捷径了。
反转长度为3的子数组：隔位交换与分组排序判定
牛客周赛127我赛时卡在B题上将近二十分钟说出去有点丢人但复盘之后我觉得这二十分钟花得值——这题的套路绝对不只适用于牛客这一场。题面核心就一句话给一个数组每次可以把一个长度为3的连续子串反转问能不能让整个数组变成有序。听上去像模拟题实际上只要看穿“反转长度3”这个操作的本质十行代码就能解决。这篇复盘我把完整的推导过程、代码实现和赛时踩的坑都写出来给被B题折腾过的同学也给自己留个存档。1. B题长什么样一个看似暴力能解的陷阱1.1 题面还原与我的第一反应先说题面。按我赛时的记忆版本大概是这样的给定一个长度为 n 的数组 an 的范围在本场大概是几千到十万这个量级元素可能有重复。允许的操作只有一种——选择一个长度为 3 的连续子数组原地反转它的顺序也就是[x, y, z]变成[z, y, x]。操作可以执行任意多次每次可以作用于任意位置。问最终能否把整个数组变成非递减顺序也就是排序后的样子。我第一反应是这不就是不断交换相邻元素吗因为反转长度3不就是把两边的元素互换一下那是否存在一个类似“冒泡排序”的构造只要我找到合适的交换序列就能排好顺着这个思路我甚至考虑过用 BFS 搜索状态空间但很快就否了——n 稍微大一点状态数根本没法枚举。而且题目问的是“能否”不是“最少几步”这通常意味着背后存在一个判定条件一旦想清楚条件代码会非常简单。后来在牛客讨论区逛了一圈发现不少人和我一样卡在“把反转拆解成若干相邻交换”的惯性思维里。还有人提到这题和 LeetCode 周赛430里某道题的套路很像都是“距离为2的交换”。当时没细看但核心思想确实是一致的操作影响的范围决定了哪些元素可以互换哪些元素永远隔着一道墙。1.2 为什么暴力模拟和贪心都不靠谱有人可能会说我直接从头到尾扫描遇到逆序就就地反转一次不行吗这题的危险之处就在这里贪心很容易给你一个“差不多对”的错觉。举个例子数组是[3, 2, 1]你看到3 2反转前三个得到[1, 2, 3]恰好成功。但数组是[5, 1, 4, 2, 3]呢从头贪心反转很可能陷入局部调整最后却差那么一个元素排不进去。因为长度3的反转不是任意交换它每次固定的交换位置是i和i2中间那个位置反而不动。如果你没有意识到这个约束就会高估自己的操控能力。并且操作次数理论上无限搜索和贪心都依赖“最优解”的概念而这题根本没有步数限制只需要一个存在性判定。所以正确的打开方式不是模拟操作过程而是分析操作本身的代数性质找出它不改变什么。这就像玩魔方你不需要真的去转几百步先搞清楚哪些色块永远只能待在哪些面上问题往往瞬间就瓦解了。2. 长度3反转的数学本质隔位交换2.1 手动实验把反转等价写成交换先把操作抽象出来。对下标i, i1, i2三个位置原来的值是[a, b, c]反转后是[c, b, a]。比较一下就能发现位置i的值变成了原来的c等于位置i2的值位置i2的值变成了原来的a等于位置i的值位置i1的值还是原来的b根本没有变化。所以“反转长度3的连续子串”在数学上就是一句话交换下标相差2的两个位置上的元素中间那个元素纹丝不动。这不是近似而是严格的等价关系。以后看到形如“反转子数组”的操作先别急着套全区间反转的模板先看长度长度是3、是4、是5结论完全不同。我把这个观察写下来之后脑子里立刻蹦出一个图像整个数组的下标被染成两种颜色偶数下标一类奇数下标一类。一次操作交换的是同色格子里的两个元素永远不会让一个元素从偶数字格跳到奇数字格里。这意味着阵列被分成了两个独立的“抽屉”操作只能在抽屉内部搬东西。2.2 不变量奇偶下标分组不可跨越这个“不变量”是整个题目的灵魂。无论你怎么操作或者操作多少次下面两个事实始终成立原来在偶数下标上的元素未来一定还在某个偶数下标上原来在奇数下标上的元素未来一定还在某个奇数下标上。用集合的语言说设E是原数组偶数下标位置的元素集合O是奇数下标位置的元素集合那么任意可达的数组它的偶数下标位置装的一定还是E这个多重集奇数下标位置装的一定还是O这个多重集。元素的值可以变位置但不可以变组别。很多同学看到这里会问那是不是就完事了只要判断原数组和目标数组在偶数位置集合、奇数位置集合上分别相等就能判定可达对这就是题目的骨架。但还有一层需要证明同一个组内部是不是任意排列都能做到毕竟我们只有“交换相距为2的两个元素”这一种操作万一偶数位内部的某些排列永远无法实现呢这就是下一节要解决的问题。3. 可达性判定从“隔位交换”到“分组排序”3.1 三步交换法证明同组内任意两元素可交换为了严谨我需要证明任取两个偶数下标的元素无论它们隔得多远都可以通过若干次长度3的反转完成交换而且不影响其他元素。直接给结论距离为2的两个位置一次反转就能互换距离为4的两个位置三次反转就能互换且其他元素全部复位。拿下标i和i4举例假设四个位置初值是[x, y, z, w, v]其中x在iy在i1z在i2w在i3v在i4目标是交换x和v。第一次反转区间[i, i1, i2]交换x和z序列变成[z, y, x, w, v]第二次反转区间[i2, i3, i4]交换x和v序列变成[z, y, v, w, x]第三次反转区间[i, i1, i2]交换z和v序列变成[v, y, z, w, x]。看最后的结果x去了i4v去了i中间的y、z、w全部回到了原位。这一步很关键它告诉我们隔4位的交换可以干净利落地完成。至于隔6位、隔8位可以用同样的思想逐步“搬运”本质上和冒泡排序里的相邻交换一样同奇偶内部任意排列都能构造出来。所以充分性成立偶数位置元素可以被重排成这组元素对应的任意顺序奇数位置同理。3.2 目标有序数组的唯一候选结构有了上面的结论整个问题就变成了给定两个独立的子序列分别由原数组偶数下标的元素和奇数下标的元素组成要求把它们重新交错放回原来的位置能否构成一个非递减数组注意如果最终要整体非递减那么偶数位置子序列内部必须非递减奇数位置子序列内部也必须非递减。因为两个相邻的偶数下标位置中间夹着一个奇数下标虽然直接看它们不相邻但在整个数组里偶位置序列是交错排列的如果两个偶位置元素e1 e2且e1在e2左边那么无论中间奇数位置的值是多少这个数组都不可能整体非递减。奇数位置同理。因此最终的有序数组即使存在其结构也是被唯一确定的把原数组偶数下标的元素全部取出来排序奇数下标的元素全部取出来排序然后按原来的下标交错拼接。如果拼接出来的数组已经非递减那么答案就是“能”如果这样都不行那换个排列方式只会更乱不存在其他可能的成功方案。这里我多说一句为什么要“分别排序”。有人可能觉得反正元素值一样排不排序无所谓。但数组元素可能有重复而且排序能让我们把“可行性”压缩成一个可检查的确定性数组而不是在一堆排列里大海捞针。对单调性判断来说排序后的组合就是最乐观的情况如果最乐观的情况都无法满足非递减那其他任何排列都满足不了。4. 代码实现核心逻辑其实只有十行4.1 先写可读性最强的Python版本我把判定逻辑写成 Python结构非常清晰def can_make_sorted(a): n len(a) even sorted(a[0::2]) odd sorted(a[1::2]) res [] ei oi 0 for i in range(n): if i % 2 0: res.append(even[ei]) ei 1 else: res.append(odd[oi]) oi 1 return all(res[i] res[i1] for i in range(n-1))a[0::2]取所有偶数下标元素a[1::2]取所有奇数下标元素。排序后交错放回最后判断整个数组是否非递减。复杂度是O(n log n)对十万量级的数据完全够用。如果 n 很小比如小于3这段代码也自动处理了偶数下标元素只有位置0奇数下标元素可能没有或只有位置1排序交错后等于原样判断。4.2 同样的逻辑用 C 实现牛客周赛很多同学习惯用 C 交写法如下#include bits/stdc.h using namespace std; bool canMakeSorted(vectorint a) { int n (int)a.size(); vectorint even, odd; for (int i 0; i n; i) { if (i % 2 0) even.push_back(a[i]); else odd.push_back(a[i]); } sort(even.begin(), even.end()); sort(odd.begin(), odd.end()); vectorint res(n); int ei 0, oi 0; for (int i 0; i n; i) { if (i % 2 0) res[i] even[ei]; else res[i] odd[oi]; } for (int i 0; i 1 n; i) { if (res[i] res[i 1]) return false; } return true; }这里唯一要注意的是几个空指针类的边界odd可能为空比如 n1 时但排序空数组没问题交错循环里oi也不会越界因为奇数下标不存在就不会走到odd[oi]。C 的sort对空 vector 是安全的。4.3 复杂度分析与一个计数特例时间复杂度O(n log n)空间复杂度O(n)。排序是主要开销如果 n 到二十万C 几毫秒就能跑完Python 也完全在可接受范围。不过赛场上我后来发现一个更快的写法。如果题目明确说数组里只有 0 和 101串版本排序判定可以退化成纯计数不需要真的排序。设整个数组里 0 的个数是k目标有序数组应该是前k个位置全是0后面全是1。因为偶位置和奇位置不能互相交换只需要检查原数组偶数下标位置上的0的数量是否等于前k个下标中偶数下标的数量奇数下标上的0的数量是否等于前k个下标中奇数下标的数量。写成公式就是偶数位0的个数必须等于(k 1) // 20-indexed 下前 k 个位置中偶数下标数量奇数位0的个数必须等于k // 2。这个特例在很多类似题里会出现遇到01串别傻傻排序两行统计就过去了。5. 赛时踩坑与边界用例复盘5.1 第一次WA我只排序了偶数组赛时我的第一版代码只对偶位置子序列排了序奇数位置保持原样就直接判断了。结果当然WA。原因很直白奇数位置内部也是可以自由重排的我忽略了这一半的操控能力。举个例子数组[3, 1, 2]偶位置是3, 2排序后变成[2, 1, 3]判断互相比较发现不有序就返回 false。但如果把奇数位置1也考虑进去奇数位置只有一个元素排列不变结果仍然是[2, 1, 3]所以这个例子的确应该是 false。换成[3, 2, 1]呢偶位置3, 1排序后是[1, 2]奇数位置2不动得到[1, 2, 3]成功。这里的关键是两边都要参与重排漏掉任何一边都会造成误判。5.2 第二次WA忘记检查整体非递减第二版我把两边都排序了但没有做“交错放回”这个动作而是直接把排序后的偶数组、奇数组拼接成一个新数组去判断。这等于改变了元素在整体数组中的位置结构。比如原数组长度6偶数组有三个数、奇数组有三个数我把它们拼接成“前三个是偶数组后三个是奇数组”这和实际交错排列完全不是一回事。正确做法必须按照原下标 0、1、2、3... 逐个填充先放偶数组第一个再放奇数组第一个再放偶数组第二个以此类推。这一步提醒我这类题的“重排”不是整体重排而是保持固定插槽位置的局部重排。5.3 边界用例与重复元素问题再说几个容易翻车的边界情况。数组长度 n1 或 n2 时根本不存在长度为3的连续子串一次操作都做不了所以只能判断原数组是否有序。我的代码天然覆盖排序空数组后交错放回结果就是原数组判断逻辑自动生效。重复元素也很容易出问题。比如[2, 2, 1, 1, 2, 2]偶位置元素集合是{2, 1, 2}排序后[1, 2, 2]奇位置元素集合是{2, 1, 2}排序后[1, 2, 2]。交错得到[1, 1, 2, 2, 2, 2]有序答案是 true。这里排序是有序数组的构造过程重复元素不需要特殊处理只要你把所有同值元素当成无差别个体看待就行。问题的关键是防止自己把重复元素用于区分奇偶分组——哪怕两个值相同的元素一个在偶组、一个在奇组它们仍然不能互换位置因为值相同可以掩盖位置差异但这个差异对“能否构造”没有影响所以不用区分。5.4 比赛群里的联想LeetCode周赛430的近似套路赛后看讨论有人提到这题的“隔位交换”和 LeetCode 周赛430的某道题思路很像。我没有去细翻那道题的题号但可以确认的是这种“限制操作距离固定”的题型在各大周赛里出现频率极高。套路一般是三步走分析单次操作等价于哪些位置交换提炼出不可跨越的分组对每个分组独立处理后判断整个结构是否满足目标性质。能迁移这个框架比背一道题有用得多。6. 通用套路总结子串操作先找不变量6.1 如何快速识别这类题以后再遇到“每次操作可选一个子数组做XXX反转/旋转/位移问能否变成目标序列”我的建议是别急着写模拟先做两件事。第一把单次操作写成最细粒度的等价形式。比如“反转长度3”展开为“交换位置i和i2”“反转长度4”可能是“交换i和i3、i1和i2”的组合长度不同结论会有巨大差异。第二找出操作无法跨越的“墙”。只要元素被分成两个或多个互不流通的组题目就从“全排列搜索”降维成“分组判定”。这种思路在 Git 仓库里有个很形象的类比两个分支之间不允许 merge只能在各自分支内部乱序提交然后问最终整个仓库的文件版本序列能不能排成某个顺序。答案就是看两个分支的内部内容是否和期望序列匹配。6.2 变式迁移如果操作是反转长度4把这套方法迁移到变式上比如“每次反转长度为4的连续子数组”。单次反转[a,b,c,d]得到[d,c,b,a]等价于两对交换a和d互换b和c互换。第一对是下标差3奇偶性不同第二对是下标差1奇偶性也不同。这就有意思了——它不是隔位交换而是“交界交换”可能所有元素全部打通也可能形成另外一个分组结构。处理方式依然是先写出等价交换对再分析这些交换对构成的图上的连通分量同一连通分量的元素可以任意互换判定就转化为各连通分量的元素集合比较。我不展开完整推导但方法框架是一致的。6.3 最后分享一个实操小技巧我个人习惯在写这类题之前先在草稿纸上列一个极小的例子比如 n5手动把一次操作的前后状态写出来标出哪些下标发生了元素移动。这个动作只需要三十秒却常常能直接看出分组。很多同学直接上代码最后被样例卡住才回来推规律反而更浪费时间。赛场上时间紧更要先动笔后写码。这题的收获对我来说不只是 AC 本身更是一种提醒操作类题目中的“操作”往往不是给你模拟用的而是给你分析用的。抓住不变量复杂的数据流动瞬间就变得清楚。下次在牛客周赛再碰到“连续子串”相关的操作题我大概能更快地找到那条通往结论的捷径了。
