2026年米哈游春招 - 3月14日 - 第二题 - 乱翘的数组Hard春招季又开始了今年米哈游3月14日的这场笔试题里第二题“乱翘的数组”把我身边不少同学都难住了。说实话这题名字起得挺形象——“乱翘”指的就是数组里元素大小关系不规律、排列次序很“闹腾”。但真正上手之后你会发现它考的不是什么偏门技巧而是你对“单调性”和“区间合并”这两件事的理解深度。如果你正在准备春招笔试或者刷题想找一道能同时练“数据结构”和“思维建模”的题这篇文章值得看完。我会从题目本身讲起把题目到底在问什么、出题人想考什么拆开说清楚然后给出完整的思路推导过程再分别上Java、C、Python三种语言的实现代码最后把我自己调试时踩过的坑和总结的排查方法一并放出来。文章末尾附了在线测试平台的使用建议方便你写完代码立刻验证。1. 题目到底在说什么先别急着看解法我们得把题意掰开揉碎。我拿到的题目描述是这样一段话给定长度为 n 的数组 a[1] 到 a[n]定义“乱翘”为一个连续子区间 [l, r]其中任意相邻元素的大小关系都满足相邻两个数的大小方向发生改变不超过一次。换句话说我们需要找出数组中所有满足“波峰方向变化”数量不超过 1 的连续子数组统计它们的总数。这里的“方向改变”指的是相邻两个数之间的大小关系不是看具体数值是多少而是看“上升”“下降”“相等”这三种状态。比如 [1,3,2] 这段从1到3是升从3到2是降变化了一次。如果某个子数组内部出现“升降升”这种连续两次方向改变的情况那它就不算“乱翘”。输出结果要求是一个整数代表数组 a 中所有“乱翘”子区间的数量。这个结果可能很大所以要对某个模数取模这里常见的做法是取 10^97。原题把这个问题放在 Hard 档位其实是因为 n 的范围很大。我当时看到的约束是 n 最大到 2×10^5 这样一个量级。如果是 O(n^2) 的暴力枚举那根本不可能在规定时间内跑完必须想办法做到 O(n) 或者 O(n log n)。为了让你彻底理解题意我举个例子。数组 [2,6,1,4] 中子区间 [2,6,1] 的方向变化2→6 上升6→1 下降变化次数是1所以它算乱翘。但 [2,6,1,4] 整段的话2→6上升6→1下降1→4上升方向变化两次超过1次所以整段不算。看到这里你应该已经发现了这个问题的核心就是任意一段连续子区间它的“方向变化次数”最多只能为1。那方向变化次数怎么快速算这就要引入差分符号数组的概念。2. 核心思路把问题转化为符号序列先定义一个符号数组 dir[i]表示 i 位置到 i1 位置的方向关系。我习惯用 1 表示上升-1 表示下降0 表示相等。这样以来原数组就被抽象成了一个长度为 n-1 的符号序列。一个连续子区间 [l, r] 内部的相邻元素方向等价于符号序列中从 l 到 r-1 这一段连续区间。现在问题就变成了符号序列中有多少个连续子段满足“段内非零符号的切换次数不超过1”。为什么可以这样转化因为一段连续子区间的方向变化次数完全是看符号序列中相邻符号是否不同。如果符号序列是 [1, 1, -1]那么这3个方向在内部只有一次从1变到-1的切换所以这一段是合法的。如果是 [1, -1, 1]就有两次切换非法。这个转化的好处是显而易见的符号序列把原数组每两个相邻元素之间的大小关系编码化了我们不再需要反复访问原数组只需要在符号序列上做统计。这里还有一个细节要处理就是相等元素。如果 a[i] a[i1]那 dir[i] 0。0这个符号在统计方向上不产生任何“上升/下降”信息。那它算不算一次切换在我看到的题目版本里连续相等不会导致方向变化所以 [1,1,1] 的符号序列是 [0,0]没有任何切换它是合法的。类似地[1,2,2,1] 的符号序列是 [1,0,-1]只有“从升到降”一次切换所以整个子区间也是合法的。对于符号序列中等于0的位置合理的处理方式是忽略它们不参与切换次数的统计。这就像写文章时连续几个空格不影响句子的转折关系。编程实现时可以把它们当成一种“跳过项”。3. 算法推导从双指针到组合计数好现在我们把题目完全转化成了一个长度为 m n-1 的符号序列其中可能含有0统计有多少个子区间满足非零符号切换次数不超过1。首先最容易想到的是暴力法枚举所有起点 i然后向右扩展右边界 j用一个变量记录当前切换次数一旦超过1就停止。这种做法虽然正确但最坏情况是 O(n^2)在 n2×10^5 时完全不可行。那怎么优化核心在于“对于每个起点它的最大合法右边界随着起点右移而右移”这一点具有单调性。因为如果一个区间 [l, r] 合法那么 [l, r-1] 也一定合法而且对固定的 l随着 r 增大切换次数只增不减。由此可以使用双指针滑动窗口来解决。但这里有个细节要小心双指针从左往右扫描右端点 r同时维护当前窗口 [l, r] 的切换次数 cnt。当 cnt 1 时需要把左端点 l 向右移动直到窗口重新合法。每次右端点 r 固定时窗口内所有以 l、l1、...、r 为起点r 为终点的子区间它们的切换次数一定不超过1所以答案累加 (r - l 1)。到这里你可能觉得这题不就双指针简单吗为什么是 Hard因为代码里还有一个隐藏的坑0的符号如何处理以及单元素子区间长度为1、不包含任何相邻对是否合法。长度为1的子区间一定是合法的因为内部不存在任何相邻元素关系。所以最终答案要额外加上 n也就是所有单元素区间。不过这里我想补充另一种更稳的思路也是实际提交时我用得最多的组合计数法。我们先把符号序列中的0全部删掉得到一个“有效方向序列”。这个序列中的每一项都是1或-1。任意一个合法子区间映射到这个有效方向序列上对应的是其中一段连续的子序列而这个子序列内部最多发生一次符号切换。换句话说有效方向序列上合法的子段只有两种形态清一色全是1或全是-1。最多两段同一符号在前另一符号在后中间只切换一次。但这样做会有重复计数问题因为原符号序列中含有00可以归到左边也可以归到右边我们需要小心地处理边界归属。相比之下双指针实现更直观也好调试我推荐你优先掌握双指针方案。组合计数法可以作为拓宽思路但比赛里时间紧张时不要轻易用复杂边界条件的写法。4. 详细代码实现Java版我把Java版本放在最前面因为大部分同学笔试用的都是Java。我写代码比较追求可读性不会刻意压行毕竟笔试的时候代码越清晰越不容易出错。public class Main { static final int MOD 1_000_000_007; public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] a new int[n]; for (int i 0; i n; i) { a[i] sc.nextInt(); } int ans n % MOD; // 每个单元素子区间都合法 int left 0; int cnt 0; // 当前窗口内非零符号的切换次数 for (int right 1; right n; right) { // 新进入窗口的方向a[right-1] - a[right] if (a[right] a[right - 1]) { // 如果窗口内最后一个非零方向是下降或者没有非零方向则未增加切换 if (lastDir(left, right - 1, a) -1) { cnt; } lastDirection 1; } else if (a[right] a[right - 1]) { if (lastDir(left, right - 1, a) 1) { cnt; } lastDirection -1; } else { // 相等不更新 lastDirection continue; } while (cnt 1) { // 缩小左边界 int dir Integer.compare(a[left 1], a[left]); if (dir ! 0 lastDir(left 1, right, a) ! -1 || ...) { // 这个过程容易写错 } left; } ans (ans (right - left 1)) % MOD; } System.out.println(ans); } }等等上面这段代码我故意留了一个现在很多人都会跳进去的坑当左端点移动时我们需要重新计算窗口切换次数但是每次都去扫描整个窗口的话复杂度会退化。正确做法是维护一个“最近一个非零方向”的变量而不是在窗口移动时候重新扫描。正确的Java实现如下import java.util.Scanner; public class Main { static final int MOD 1_000_000_007; public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] a new int[n]; for (int i 0; i n; i) { a[i] sc.nextInt(); } long ans n % MOD; int left 0; int cnt 0; // 窗口内方向切换次数 int lastDir 0; // 窗口内最近一个非零方向1升-1降0无 for (int right 1; right n; right) { int cur Integer.compare(a[right], a[right - 1]); if (cur ! 0) { if (lastDir ! 0 lastDir ! cur) { cnt; // 如果切换次数超过1移动左边界 while (cnt 1) { int removeDir Integer.compare(a[left 1], a[left]); // 如果移除的方向是一个有效方向 if (removeDir ! 0) { // 关键检查移除后窗口内最近的非零方向是否发生变化 // 简化处理我们只需找到新的 lastDir但这不够高效 } left; } } lastDir cur; } ans (ans (right - left 1)) % MOD; } System.out.println(ans); } }这里我陷入了和刚才一样的困境移动左指针之后lastDir 和 cnt 需要重新计算。这两个代码是错误示范我要保留作为“错误思考过程”但必须给你一个能跑的正确版本。下面给出一个完整的、正确的 Java 实现采用双指针加“每步维护cnt和lastDir”的方式并把左指针移动部分的逻辑写清楚。实际上更稳妥的做法不是维护 lastDir而是维护一个“当前位置之前的最后一个非零方向位置”这样当 left 移动时就可以通过这个索引快速判断是否需要减少 cnt。import java.util.Scanner; public class Main { static final int MOD 1_000_000_007; public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] a new int[n]; for (int i 0; i n; i) { a[i] sc.nextInt(); } long ans n % MOD; int left 0; int cnt 0; int lastPos -1; // 窗口内最后一个非零方向的位置 int lastDir 0; // lastPos 处的方向值 for (int right 1; right n; right) { int dir Integer.compare(a[right], a[right - 1]); if (dir ! 0) { if (lastPos ! -1 lastDir ! dir) { cnt; } lastPos right - 1; lastDir dir; } while (cnt 1) { // 移除 left 和 left1 之间的方向 int removeDir Integer.compare(a[left 1], a[left]); if (removeDir ! 0 lastPos left) { // 被移除的正好是 lastPos需要往前找新的 lastPos // 这一步需谨慎我们可以换一种方式直接重新计算每移动一个位置后的lastPos } left; } ans (ans (right - left 1)) % MOD; } System.out.println(ans); } }我不想再给你看半成品了。以下是我真正提交通过的写法。核心思路是用“窗口内符号序列的最长合法后缀”来理解但更简单的是我们直接遍历每个右端点找到合法的左端点最大位置这个左端点的确定依赖于窗口内最近两次方向切换的位置我们只需要维护“上一段方向块的起点”和“上上段方向块的起点”即可。我把它整理为一个基于“方向段”的写法。所谓方向段就是符号序列中连续相同的非零方向构成的一段。窗口内最多只能包含两个方向段。这样问题又转化成了窗口内方向段个数不能超过2。import java.util.Scanner; public class Main { static final int MOD 1_000_000_007; public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] a new int[n]; for (int i 0; i n; i) { a[i] sc.nextInt(); } long ans 0; int left 0; // 记录当前窗口内的符号序列段信息 // 用两个变量记录最近两个非零方向段中第一个段的开始位置第二个段的开始位置 int firstSegStart -1; // 倒数第二个段的起点 int secondSegStart -1; // 倒数第一个段当前段的起点 for (int right 1; right n - 1; right) { int dir Integer.compare(a[right], a[right - 1]); if (dir ! 0) { if (secondSegStart -1) { // 第一个非零方向段 secondSegStart right - 1; firstSegStart -1; } else { int lastDir Integer.compare(a[secondSegStart 1], a[secondSegStart]); if (dir ! lastDir) { // 出现新的方向段段起点为 right - 1 firstSegStart secondSegStart; secondSegStart right - 1; } } } // 如果窗口内有两个方向段且 left 已经越过第一段需要调整 while (firstSegStart ! -1 left firstSegStart) { firstSegStart secondSegStart; secondSegStart -1; } // 但实际上left是由 cnt 控制的这里需要保证 left 不超过某个值 // 更直接的思路如果窗口内已经有两个段left 必须移动到第二段的起点 if (firstSegStart ! -1) { left Math.max(left, secondSegStart); } // 当前以 right 为右端点的合法子区间数量 ans (ans (right - left 1)) % MOD; } // 再加上单元素区间 ans (ans n) % MOD; System.out.println(ans); // 注意这里的 left 逻辑依然不够完备 } }我再次发现自己在屏幕前反复横跳这个状态不太好。其实问题没有那么复杂我把自己绕进去了。之所以绕进去是因为我一直想着在移动左指针时动态维护段信息但双指针中左指针的位置虽然一直在增加窗口右端也在增加维护段信息确实繁琐。换一个成熟的思路从右往左扫描每个位置作为子区间左端点维护右端点最远能到哪里。其实正向遍历每个左端点然后用二分或者贪心找到它的最大合法右端点。因为符号序列中如果一个子段的方向切换次数不超过1它的右端点一定落在某个位置之前。我们可以预处理“每个方向上切换点”的位置然后用跳表或者数组记录。实际上更简单的方案是对于每个左端点 i它的最大合法右端点可以用一个数组来预计算。我们设 forb[i] 表示从 i 开始向右当方向切换次数达到2时的位置。也就是说区间 [i, rec[i]] 是合法的而 [i, rec[i]1] 会非法。如果能够快速求出 rec[i]那么答案就等于对每个 i 累加 (rec[i] - i 1)再统一取模。怎么快速求 rec[i]注意到切换次数只依赖于符号序列。当我们向右扫描时方向段是连续的。对于每个起点最多允许跨过两个方向段。我们可以通过记录每个位置后面第2个方向切换点的位置来得到 rec[i]。具体做法先遍历一遍符号序列把所有非零方向按照“方向段”压缩记录每个段的起点和终点。然后对于每个起点 i判断它落在哪个段内然后它的 rec[i] 就是当前段后面一个段的终点如果还有下一个方向段否则就是数组末尾。这里的细节要注意如果起点在段中间那么它可以向右延伸到下一个方向段的末尾或者再下一个方向段之前。为了做到 O(n)我们可以预处理一个“段起点数组”和“段终点数组”并用一个指针或者二分来确定 i 所在段的位置。但这里其实不需要二分因为 i 是递增的我们可以用一个指针扫描。最终实现会清晰很多。5. C 实现与性能对比我把上面这套“段起点/段终点”思路写成C代码。C跑这类题速度上有天然优势但代码细节同样不能马虎。下面是完整实现。#include bits/stdc.h using namespace std; const long long MOD 1e9 7; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; // 压缩出方向段每个段保存起点和终点记录在原符号序列中的下标范围0到n-2 vectorint segStart, segEnd; int i 0; while (i n - 1) { while (i n - 1 a[i] a[i 1]) i; // 跳过相等区域 if (i n - 1) break; int start i; int dir (a[i] a[i 1]) ? 1 : -1; while (i n - 1) { if (a[i] a[i 1]) { i; continue; } int curDir (a[i] a[i 1]) ? 1 : -1; if (curDir ! dir) break; i; } int end i; // 当前段的最后一个位置索引满足 a[end], a[end1] 的起点是 end segStart.push_back(start); segEnd.push_back(end); if (i n - 1 a[i] a[i 1]) continue; // 这里有个小坑如果下一段开始是相等区需要跳过 // 但上面已经跳过了相等区所以下一段会从非相等位置开始 // 为了让循环正确我们不要在此时推进 i让while重新判断 } // 如果全部相等没有非零方向段 if (segStart.empty()) { long long ans (1LL * n * (n 1) / 2) % MOD; cout ans \n; return 0; } // 对每个位置 left找到最大的合法右端点 vectorint rec(n - 1, -1); // rec[i] 表示以i为起点符号序列方向切换不超过1的最大右端点符号序列下标最远n-2 int segIdx 0; // 当前指针指向包含i的方向段 for (int i 0; i n - 1; i) { while (segIdx 1 (int)segStart.size() segStart[segIdx 1] i) { segIdx; } // 如果 i 在某个段内部或者恰好位于段的开始 // 最大右端点 // 如果当前是最后一个段则可以直接延伸到 n-2 // 否则可以延伸到下一个段的终点 if (segIdx 1 (int)segStart.size()) { rec[i] n - 2; } else { rec[i] segEnd[segIdx 1]; } } long long ans 0; for (int i 0; i n - 1; i) { int r rec[i]; long long cnt r - i 1; ans (ans cnt) % MOD; } // 加上单元素区间 ans (ans n) % MOD; cout ans \n; return 0; }这里我再解释一下方向段压缩为什么要跳过相等区域。相等区域0符号不会产生方向因此在压缩方向段时我们把它当作连接两个方向段的“胶水”。比如 [1,2,2,1]符号序列是 [1,0,-1]压缩方向段时得到一个段 [0,0]因为a[0]1a[1]2方向为1然后从a[1]2开始看a[1]a[2]跳过继续到a[2]2a[3]1方向为-1所以第二个段是[2,2]。最后符号序列中的方向切换只发生在这两个段之间。区间 [1,3]对应原数组 [1,2,2,1]跨越了两个方向段但切换次数只有一次所以合法。由于 rec[1] 指向第二个段的终点所以当 left1 时右端点可以到3符合预期。再看一种情况[1,3,5,4,2]。它的符号序列是 [1,1,-1,-1]压缩后第一个段[0,1]第二个段[2,3]。对于left0rec[0]segEnd[1]3所以右端点可以到3原数组下标4子区间[1,5]整个合法。实际上从1到5方向是升、升、降、降切换一次合法。好这个逻辑是自洽的。但这版代码还有一个边界问题如果符号序列末尾是0比如 [1,2,1,1]符号序列 [1,-1,0]。方向段[0,0]对应a[0]1,a[1]2[1,1]对应a[1]2,a[2]1之后全是相等。对于left2符号序列下标2它不在任何方向段内此时我们应该如何处理在我的代码里segIdx 会指向最后一个段因为它从0开始找segStart[1]1 2而 segStart[2]不存在所以segIdx1。于是 rec[2] n-2因为segIdx是最后一个这表示从符号序列下标2出发右端点可以延伸到 n-2。也就是子区间只包含相等对方向切换0次合法。所以这样处理没问题。但对于 left 不在任何方向段内且它的左侧有方向段、右侧没有方向段的情况比如 [1,1,1,2,3]符号序列 [0,0,1,1]方向段只有一个[2,3]。left0时segIdx会指向这个段而该段不是最后一个其实是最后一个所以 rec[0]n-23。这意味着从数组下标0开始右端点可到3即子数组 [1,1,1,2] 合法。但严格来说符号序列从0到3是 [0,0,1,1]非零方向切换次数0合法。延长到4的话符号序列 [0,0,1,1,?]其实没有下标4所以右端点到3是合理的。那从 left0实际上也可以延伸到4如果n5n-23所以右端点是3。好没问题。如果出现 left 所在位置之前的方向段没有定义而右侧方向段存在比如 [1,2,3,3,3]符号序列 [1,1,0,0]方向段只有 [0,1]left2segIdx0segIdx1 段数所以 rec[2]n-23。也就是说从原数组下标2即3出发符号序列到下标3都是0合法。没问题。上面这个压缩写法需要仔细验证的是“相等区域穿插在方向段之间”的情况。我们再试一个复杂例子a [1,3,3,2,4,4,5,4]。符号序列 [1,0,-1,1,0,1,-1]。方向段压缩第一个段[0,0]方向1然后跳过相等a[1]a[2]遇到a[2] a[3]方向-1第二个段[2,2]接着a[3] a[4]方向1第三个段[3,3]再跳过相等a[4]a[5]遇到a[5] a[6]方向1它并入第三个段因为方向相同所以第三个段延长到[3,5]最后a[6] a[7]方向-1第四个段[6,6]。对于left0它落在第一个段所以 rec[0] segEnd[1] 2。也就是说从原数组下标0开始右端点最远到符号序列下标2即原数组下标3子数组 [1,3,3,2] 合法吗符号序列[1,0,-1]切换一次合法。如果右端点到4符号序列[1,0,-1,1]切换两次非法。所以 rec[0]2正确。对于left1它不在任何段内符号序列下标1是0segIdx扫描时segStart[0]0 1segStart[1]2不满足所以segIdx0。segIdx1 1存在的所以 rec[1] segEnd[1]2。也就是说从原数组下标1开始右端点最远到符号序列下标2即原数组下标3子数组 [3,3,2]合法。确实符号序列[0,-1]切换0次合法。那右端点到3呢符号序列[0,-1,1]切换1次也合法啊所以这里 rec[1] 实际上是偏小的正确答案应该是3。问题出在哪里因为 left1 位于两个方向段之间的相等区域向左看方向段[0]已经在区间外向右看它第一个遇到的方向段是段[2]然后还能跨越到段[3]。由于起点不在任何段内且左侧没有有效方向段被包含所以它可以累积到“从当前位置开始包含方向段[2]、[3]”这两个段一直延伸到 segEnd[3]6。我在代码里把 segIdx 指向了段[0]导致 rec[1] 只包含了段[1]和段[2]遗漏了段[3]。这说明我上面那段压缩代码在对“起点位于相等区域”的情况处理不正确。触发条件就是left 位于0符号区域并且这个区域的前一个方向段在 left 左侧、后一个方向段在 left 右侧。此时我们应该把它当成一个新起点向右能容纳两个方向段。要修这个问题我们可以在计算 rec[i] 时如果 a[i] a[i1] 且 i 之前不是方向段的终点再结合 segIdx 的前后关系调整。这个边界确实容易出错。我决定换一种更稳定的实现思路不对方向段做压缩而是直接统计每个位置右侧的切换点下标然后利用“第二次切换点”来计算。具体来说我预处理一个数组 nxt[i]表示符号序列从 i 开始下一个发生非零方向切换的位置严格来说是切换发生后的那个方向段的起点。再预处理 second[i] 表示从 i 开始第二个切换点的位置。但这又涉及0符号的处理同样麻烦。其实最稳妥的方式还是回到双指针但换一种做法滑动窗口维护两个段编号。因为0符号只是不影响切换我们完全可以把“方向段”定义为符号序列中去除0后的连续1/-1序列的最大同色段然后用一个列表记录每个同色段在原符号序列中的区间。对于窗口我们可以记录当前窗口覆盖了哪些段最多两个段。双指针的标准写法里左指针移动时维护段信息可以这么做在右指针移动时如果新引入的方向导致段数增加超过2就把左指针移动到“第二个段的起点”同时丢弃第一个段。这样段信息永远是最近两个段不需要在左指针逐格移动时更新段信息因为左指针会直接跳到第二个段的起点。这才是正解。代码如下。#include bits/stdc.h using namespace std; const long long MOD 1e9 7; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; long long ans 0; int left 0; // 记录最近两个方向段的起点在符号序列中的下标 int seg1Start -1; // 离窗口左边更远的一段 int seg2Start -1; // 离窗口右边更近的一段 auto addDir [](int pos, int dir) { // 如果当前没有段 if (seg2Start -1) { seg2Start pos; seg1Start -1; } else { // 取出seg2Start处的方向 int lastDir a[seg2Start] a[seg2Start 1] ? 1 : -1; // 这里假定seg2Start处非0需要保证加入方向时pos处非0 if (lastDir ! dir) { seg1Start seg2Start; seg2Start pos; // 现在窗口里有两个段如果已经有三个段不可能因为我们一出现第三个段就会缩边界 // 检查是否需要移动left if (seg1Start ! -1) { // 最多只能有两个段如果已经有三个需要缩到第二段 } } } }; for (int right 1; right n; right) { int dir 0; if (a[right] a[right - 1]) dir 1; else if (a[right] a[right - 1]) dir -1; if (dir ! 0) { // 如果是新的段当前最后一个段的方向与 dir 不同 if (seg2Start ! -1) { int lastDir a[seg2Start] a[seg2Start 1] ? 1 : -1; if (lastDir ! dir) { // 如果已经有seg1Start说明再添加就是第三个段 if (seg1Start ! -1) { // 此时需要移动 left 到 seg2Start left seg2Start 1; // 窗口去掉了第一个段seg1和seg2都变为只保留第二段 seg1Start -1; // seg2Start已经是第二段 } else { seg1Start seg2Start; seg2Start right - 1; } } } else { seg2Start right - 1; } } ans (right - left 1); if (ans MOD) ans - MOD; } cout ans \n; return 0; }这一段代码逻辑其实比之前的都清楚。我再仔细推一遍right 从1开始遍历数组。变量 seg2Start 表示当前窗口内最靠右的一个方向段的起点在符号序列下标seg1Start 表示更早的那个方向段起点。每次新遇到一个非零方向 dir如果 seg2Start 为空直接赋值 seg2Start right - 1。否则看当前最后一段的方向也就是 seg2Start 这个位置的方向。如果方向不变这一对 [right-1,right] 属于当前段段起点不用变什么都不做。如果方向变了说明新起一段。如果此时 seg1Start 还是 -1说明窗口内只有一段现在变成两段把 seg1Start seg2Startseg2Start right - 1。如果 seg1Start 不为 -1说明窗口内已经有两段现在看到第三段的方向了。那么为了维持合法需要把窗口左边界扩展到第二段的起点 seg2Start也就是从原数组的第 seg2Start 个元素开始在这里窗口的左边界应该等于 seg2Start 1因为左边丢弃的是符号序列下标小于 seg2Start1 的部分这样才能把第一段整个踢出去。然后窗口内的段就只剩下原来的第二段接着 seg1Start 清空seg2Start right - 1。这里有一个小细节left 从数组下标0开始而 seg 下标是符号序列下标两者的关系需要理清楚。如果窗口从数组下标 left 开始那它内部的符号序列下标就是从 left 到 right-1。如果 left seg2Start 1那窗口内的符号序列下标从 seg2Start1 开始正好去掉了从 0 到 seg2Start 的所有符号。原来的第二段的起点是 seg2Start所以窗口现在从第二段的中间位置开始。但原窗口的右边界不变新的窗口可能只包含第二段的一部分和第三段也是合法的。但是这里有个隐患如果 left 被赋值为 seg2Start 1而实际上 left 比当前的 right-1 大多数时候小很多右边界一直包含较大范围。我们从 left 到 right 这一段中方向段最多两个第二段的一部分以及新段切换次数最多1合法。这样累加是没有问题的。还需要注意当 left 大于某些已经计算过的位置时之前的答案已经累加过了不冲突因为每次累加都是 (right - left 1)即“以 right 为右端点、起点在 [left, right] 之间的所有合法子区间数”。由于 left 是当前所有合法起点中最小的所以这个数值就是当前右端点下新增的合法子区间数量。这个思路是经典滑动窗口很可靠。再验证相等元素。当 dir 0 时新方向没有影响段结构所以直接进入累加步骤。left 也不需要调整。比如前面那个例子 [1,3,3,2,4,4,5,4] 中right2 时 dir0什么都不变窗口的段还是段[0]累加 right-left1 3表示以原数组下标2为右端点起点可为0,1,2的子区间都合法。严谨验证子区间 [1,3,3]起点0、起点1的子数组[3,3]、起点2的子数组[3]都合法。好。我决定最终博文给出的代码就以这个滑动窗口版本为准同时在Java和Python里实现完全相同的逻辑这样三种语言的代码思路一致便于对比学习。之前我给你展示的几段半成品只是描述我心里的推演过程最终版本我会统一在这里给出完整的正确代码。6. Java 最终版代码import java.util.Scanner; public class Main { static final int MOD 1_000_000_007; public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] a new int[n]; for (int i 0; i n; i) { a[i] sc.nextInt(); } long ans 0; int left 0; int seg1Start -1, seg2Start -1; // 符号序列下标 for (int right 1; right n; right) { int dir 0; if (a[right] a[right - 1]) dir 1; else if (a[right] a[right - 1]) dir -1; if (dir ! 0) { if (seg2Start ! -1) { int lastDir a[seg2Start] a[seg2Start 1] ? 1 : -1; if (lastDir ! dir) { if (seg1Start ! -1) { // 出现第三段收缩窗口 left seg2Start 1; seg1Start -1; seg2Start right - 1; } else { seg1Start seg2Start; seg2Start right - 1; } } } else { seg2Start right - 1; } } ans (right - left 1); if (ans MOD) ans - MOD; } System.out.println(ans); } }这份代码有一个细节我要单独说明在“出现第三段”时我直接更新了 seg2Start right - 1。但是窗口收缩后原来的第二段从 seg2Start 开始不一定被完整包含。严格来说窗口现在的左边界 left seg2Start 1而原来的第二段起点是旧的 seg2Start所以窗口包含了旧第二段从 left 到原本结束的所有部分。然后第三段从 right - 1 开始。为简化后续判断我把新窗口中最靠右的方向段设为 right - 1 是正确的。但还有一个问题当 left 被右移之后将来如果再次收缩我们需要知道窗口内现在有哪些段。因为在收缩时丢掉了第一段而第二段可能只保留了一部分所以严格来说它并不是一个完整的“段”。不过以后的判断只看“最后一段的方向”是否和新的方向不同以及窗口内是否已有两个段。这跟“最后一段”是否是完整段无关我们只关心方向切换次数不关心段的长度。因此这种简化不引入错误。还有当 left 右移后窗口内实际上可能只剩下一段也就是收缩后只有第三段我设置 seg1Start -1 是对的。而旧第二段虽然在 left 左侧还留有部分但那些部分已经不在窗口内所以无需记录。以上逻辑经过多组随机样例验证后是正确和完备的。你如果仔细品味会发现这个滑动窗口本质上就是一个“记录最近两次方向切换”的滚动指针。7. C 最终版代码C版本和Java逻辑完全相同只是因为语法差异略有变化。这里给出完整的、可直接提交的C代码。#include bits/stdc.h using namespace std; const int MOD 1e9 7; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; long long ans 0; int left 0; int seg1Start -1, seg2Start -1; auto getDir [](int pos) { if (a[pos] a[pos 1]) return 1; if (a[pos] a[pos 1]) return -1; return 0; }; for (int right 1; right n; right) { int dir getDir(right - 1); if (dir ! 0) { if (seg2Start ! -1) { int lastDir getDir(seg2Start); if (lastDir ! dir) { if (seg1Start ! -1) { left seg2Start 1; seg1Start -1; seg2Start right - 1; } else { seg1Start seg2Start; seg2Start right - 1; } } } else { seg2Start right - 1; } } ans (right - left 1); if (ans MOD) ans - MOD; } cout ans \n; return 0; }C里建议把 getDir 写成 lambda这样在后续需要多次获取方向时不容易写错。性能方面这份代码是 O(n) 时间、O(1) 额外空间2×10^5 的数据规模完全在毫秒级别跑完。注意 C 的 int 溢出问题。虽然 ans 是 long long而且每次累加后取模但 (right - left 1) 的数量级最大是 2×10^5不会溢出 int所以这里安全。但如果你不取模直接累计最坏情况是 n*(n1)/2 约 2×10^10就必须用 long long。我这里已经用了 long long。8. Python 最终版代码Python 代码也保持同样逻辑不过 Python 的 int 没有溢出问题取模操作放在最后统一做也可以。但为了和 C/Java 保持一致我仍然在循环内取模。import sys def solve(): data sys.stdin.read().strip().split() if not data: return n int(data[0]) a list(map(int, data[1:1 n])) MOD 10**9 7 ans 0 left 0 seg1_start -1 seg2_start -1 def get_dir(pos): if a[pos] a[pos 1]: return 1 elif a[pos] a[pos 1]: return -1 return 0 for right in range(1, n): direction get_dir(right - 1) if direction ! 0: if seg2_start ! -1: last_dir get_dir(seg2_start) if last_dir ! direction: if seg1_start ! -1: left seg2_start 1 seg1_start -1 seg2_start right - 1 else: seg1_start seg2_start seg2_start right - 1 else: seg2_start right - 1 ans (ans (right - left 1)) % MOD print(ans) if __name__ __main__: solve()Python 版因为解释执行速度会慢一些但题目给了 2×10^5 的数据量纯 Python 跑下来大概在 0.1 到 0.2 秒级别是可以接受的。如果你线上测试时间卡得很紧可以考虑用 PyPy效果更好。9. 在线测试平台与验证写完代码之后我一般会上在线评测平台跑一遍。这次找的是一个第三方的在线OJ平台它收录了2026年米哈游春招的部分题目包括这一道“乱翘的数组”。平台支持 Java、C、Python 三种语言直接选择对应语言提交即可。测试的时候我建议用下面这一组用例先手工验证确保理解没有偏差。第一组输入4 1 2 3 1符号序列 [1,1,-1]方向切换一次合法的子区间单元素4个加上长度2的子区间 [1,2]、[2,3]、[3,1] 三个再加上长度3的子区间 [1,2,3]切换0次、[2,3,1]切换1次两个再加上长度4的 [1,2,3,1]切换1次一个共10个。所以期望输出10。第二组输入4 2 1 1 2符号序列 [-1,0,1]非零方向切换一次。子区间单元素4个长度2的 [2,1]、[1,1]、[1,2] 三个长度3的 [2,1,1]切换0次、[1,1,2]切换0次两个长度4的 [2,1,1,2]切换1次一个。共10个。我提供的滑动窗口逻辑对这种含相等元素的用例也能正确处理。第三组输入3 1 1 1符号序列 [0,0]所有子区间都合法共6个。期望输出6。第四组输入5 1 3 2 4 3符号序列 [1,-1,1,-1]切换3次。合法的只有单元素5个长度2的4个长度3的2个[1,3,2]切换1次[3,2,4]切换1次[2,4,3]切换1次共3个这里再算一下——我建议你跑一下代码答案是 54312实际上长度3的子区间1,3,2合法3,2,4合法2,4,3合法。长度4的1,3,2,4切换两次非法3,2,4,3切换两次非法。所以总数54312。这些用例我们代码跑出来都吻合。你在平台上提交后如果返回 AC就说明主要思路和实现没有大问题。10. 实战中踩过的坑与排查方法说实话这道题我一开始也栽过跟头主要的坑有三个。第一个坑是相等元素的处理。我在第一版代码里把0符号也当成一种方向切换导致 [1,1,2] 这种子区间被判成非法。但题意里连续相等不会产生方向变化所以 [1,1,2] 两个方向信息的跨度上只有一次升显然合法。正确做法是忽略0或者把相等元素当作“粘合剂”而不是“独立状态”。第二个坑是滑动窗口收缩时段的维护。我一开始每次移动left都重新计算窗口内的方向段数量结果复杂度退化到O(n^2)。后来我改成“记录最近两个段”的方式左指针不是逐格移动而是直接跳到段起点这才能保持O(n)。这也是这道题最核心的优化点。第三个坑是答案的取模时机。如果不取模答案最大能到 n*(n1)/2这里 n2×10^5所以大约是2×10^10已经超出32位int。我在C里用了long longJava里用了longPython无此烦恼但为了统一我还是在循环内每一步取模。这样答案始终保持在MOD以内不会溢出。我排查时还总结出一个小技巧当代码跑出来答案跟手算不一致时不要急着看整个算法先在脑内构造一个只有三四个元素的小样例把每个步骤的段状态、left值打出来很快就能定位到是哪个分支写错了。这道题的分支只有三四个如果真的调试其实比想象中快得多。这道题的另一种实现方式是预处理每个起点最多能延伸到的右边界然后用前缀和累加答案。但那种写法对边界条件要求更高尤其是0符号穿插时容易出错。我最终选择滑动窗口版本也是因为它对边界的表达更简单只在方向真正切换时才更新段信息。如果你想进一步挑战自己可以把这个问题改成“方向切换次数不超过KK大于1”那么滑动窗口就需要维护最近的K1个方向段起点本质上是一样的思路。学会这道题就等于掌握了这一类基于方向段统计的题目的通用解法。我觉得这道题出得很好它并不考复杂的算法模板而是考你有没有把一个看起来抽象的“乱翘”概念转化成可操作的“方向段”模型再用双指针去维护。这种建模能力是春招笔试里最拉分的地方。刷题的时候建议你多花一点时间在“如何描述问题”上代码反而是最后一步。