C++七级认证等价消除题：用栈将O(n²)模拟优化为O(n)一趟扫描

最近陆续有备考C七级认证的朋友来问“等价消除”这道题。说实话这道题初次看到会觉得很像游戏“消消乐”——给定一个数列只要相邻两个元素满足某种等价条件就可以消掉消掉之后原本不相邻的元素又变成相邻从而可能引发一连串新的消除。很多同学第一反应是“每次从头到尾扫一遍找到能消的就消消完再扫”这种思路实现简单可惜复杂度过高在大数据下基本必挂。这道题表面上是个模拟题实际上考察的是对栈结构的理解和建模能力。如果你能把“消除后的重新相邻”想清楚整道题的代码量可以压缩到很短时间复杂度也能做到一趟扫描。这篇文章我会从完整思路、代码实现、常见坑点、变式扩展几个角度拆开讲尽量让不同基础的朋友都能看懂、能在OJ上复现出满分做法。1. 题目定位与整体思路拆解先交代清楚问题模型。这道题最典型的描述是给定长度为 n 的整数序列每次可以找到相邻两个“等价”的元素把它们同时消除消除后左右两侧剩余元素会重新靠拢若新靠拢的两个元素也等价则继续自动消除。要求输出最终序列的长度或者输出最终剩下的序列。这里的“等价”定义不同版本略有差别。常见的有三种第一种是数值相等比如两个相邻的 5 可以消除第二种是互为相反数比如 3 和 -3 能消除第三种是两数异或结果为一个固定值。接下来我以“数值相等”为主线讲清楚核心算法后再在文末给出如何快速扩展到其它等价条件。1.1 题目真正的难点不在“找”而在“状态维护”如果只做一轮消除谁都会写遍历一遍见到相邻相等就标记删除。难点在于一轮消除后原本被拆开的元素可能会重新碰到一起第二轮还要继续处理甚至第三轮、第四轮…… 比如序列 [1, 2, 2, 1, 3]第一轮先消除中间的 [2, 2]序列变成 [1, 1, 3]紧接着 [1, 1] 又变成相邻且相等继续消除序列变成 [3]最终答案长度是 1。如果你采用“扫一轮、消一轮”的写法最坏情况下序列被消成长度 1 需要 O(n) 轮每轮扫描 O(n)总共 O(n²)。当 n 到达十万级别时这个复杂度已经没法稳定通过。所以核心突破点只有一个能不能用一种数据结构让新产生的“新相邻关系”不用重新全局扫描就能立刻被检查到。这就是栈的用武之地。1.2 为什么看到“消除”要第一反应想到栈你可以把整个过程想象成往一个竖直的罐子里依次丢元素。每丢进一个新元素 x它只会和当前罐子顶部的那个元素产生“相邻关系”。如果栈顶元素和 x 等价就把栈顶元素弹出来相当于两个元素一起抵消如果不等价x 就自己入栈。为什么这样是对的因为消除永远发生在“当前序列”中相邻的两个位置。而用一个栈维护“还没被消除的序列”栈顶正是当前序列中最后一个还没有被决定去留的元素。新加入的元素 x 如果和它等价这两个必然相邻且应该消除消掉之后x 的前一个位置又变成了栈顶元素恰好对应“消除后重新相邻”的连锁反应。这个过程实际上和“括号匹配”是同一个道理。括号匹配中遇到右括号时检查栈顶左括号是否匹配这里遇到新元素时检查栈顶元素是否等价。括号匹配能一趟解决等价消除同样能一趟解决。1.3 数据范围倒推算法复杂度正常情况下七级认证的数据范围会卡在 n ≤ 10^5 或者更大。这种范围下 O(n²) 算法很难通过需要把复杂度控制到 O(n) 或 O(n log n)。栈解法每个元素最多入栈一次、出栈一次所以总体是 O(n)空间复杂度也是 O(n)最坏情况下所有元素都无法消除栈里存下全部元素。这个复杂度是这道题的最优解层级写出来后跑大样例基本也就是几十毫秒级别。也有人想用数组配合双指针做做法是从左往右扫描维护一个“有效位置”指针遇到可消除就回退。这个思路本质还是栈只是把栈写成了数组后面我会给出代码对比。2. 核心细节解析与关键操作要点思路清楚之后真正的比赛区别往往体现在细节。尤其是一些不明显的小错误会让输出答案永远差一点点或者在边界数据上直接越界崩溃。2.1 先把“等价条件”抽象成一个函数我见过太多同学把等价判断直接写在循环里类似于if (st.back() a[i])。这样写本身没错但当题目换一种等价关系比如改成“两数和为 0”或“两数异或等于 k”时你就得在循环里翻来覆去找那行 if改起来容易漏。更规范的写法是单独抽一个判定函数inline bool equivalent(int x, int y) { return x y; // 按题目要求修改 }后面主循环里只需要调用if (!st.empty() equivalent(st.back(), x))。这样逻辑高度内聚也不容易手滑写错比较符号。这种做法在正式比赛中特别重要。因为竞赛时紧张如果等价条件散落各处调试时非常麻烦。抽成函数后哪怕题目要求改等价规则也只需要改一行。2.2 空栈判断与出栈后继续比较的关系使用栈时最经典的崩溃点就是忽略空栈。比如你直接写if (st.top() x) { st.pop(); }当栈为空时top()的行为是未定义的很可能直接段错误。正确写法要先判断非空if (!st.empty() st.back() x) { st.pop(); } else { st.push_back(x); }这里还有一个细节如果满足等价条件我们只pop()一次不需要额外写循环再和新的栈顶比较。因为外层遍历会继续处理下一个元素到时候自然会把新元素和新的栈顶比较。但有一种极易写错的嵌套写法while (条件不满足) { ... }如果你在里面写多级 while 来处理“消完一个之后继续消当前元素和新的栈顶”反而容易把自己绕晕也容易处理错。正确的做法是每个新元素只和当前栈顶比较一次要么等价弹出要么不等价入栈然后交给下一个元素。2.3 用 vector 代替 stack稳定性更好C STL 里虽然有std::stack但竞赛场景下我建议直接用vectorint充当栈。理由有三stack底层默认也是deque没有reserve能力频繁扩容会有少量额外开销vector可以提前reserve(n)避免多次内存分配。vector支持back()、push_back()、pop_back()使用起来和栈完全一样但需要调试中间状态时可以直接遍历输出非常方便。如果你需要输出最终剩下的序列vector本身就是答案容器省一步转换。很多同学担心vector会不会比stack慢实际测试下来差距微乎其微在 10^5 数据量下可以忽略不计。代码可读性和可调试性反而更重要。2.4 不要用“边删边遍历”的原地删除思路另一个很容易掉进去的坑是用vector::erase()在遍历中删除元素。for (int i 0; i (int)a.size(); i) { if (a[i] a[i 1]) { a.erase(a.begin() i, a.begin() i 2); i max(0, i - 1); // 试图回退位置 } }这个写法有两个大问题一是erase本身是 O(n) 的最坏情况下总复杂度轻松到 O(n²)二是删除后迭代器和下标全部重新变化回退逻辑很容易出错尤其是连续消除的时候i 的调整经常差一位。除非 n 非常小否则强烈不建议用这种写法。栈的做法不需要真正删除中间元素它只是把“未消除的元素”按顺序维护起来逻辑可行性要高得多。3. 可复现的满分代码与执行流程下面给出一份完整的可提交代码。以“数值相等即可消除”为标准版本C17 下编译运行时间复杂度 O(n)空间复杂度 O(n)。3.1 参考实现#include bits/stdc.h using namespace std; inline bool equivalent(int x, int y) { return x y; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n); for (int i 0; i n; i) { cin a[i]; } vectorint st; st.reserve(n); for (int x : a) { if (!st.empty() equivalent(st.back(), x)) { st.pop_back(); } else { st.push_back(x); } } cout (int)st.size() \n; // 如果需要输出最终序列可以继续输出 st // for (int i 0; i (int)st.size(); i) { // cout st[i] (i 1 (int)st.size() ? \n : ); // } return 0; }如果你不想读入整个数组也可以边读边处理不需要a数组vectorint st; st.reserve(n); for (int i 0; i n; i) { int x; cin x; if (!st.empty() st.back() x) { st.pop_back(); } else { st.push_back(x); } }两种写法等价后一种更省内存也能稍微减少一点遍历开销。不过很多选手习惯先读完整数组再处理方便构造一些特殊测试。3.2 输入输出优化与框架说明代码里ios::sync_with_stdio(false); cin.tie(nullptr);这两行建议背下来。不做这个优化有些评测环境里cin处理十万级输入会有明显卡顿加了之后基本和scanf相差不大。如果你所在的环境不支持这些设置或者更习惯 C 风格输入也可以用int n; scanf(%d, n); vectorint st; st.reserve(n); for (int i 0; i n; i) { int x; scanf(%d, x); ... }总之输入部分不是算法重点但很影响实际通过率。输出不要忘换行部分 OJ 对 末尾换行 有苛求养成打印\n的习惯。3.3 手工走查样例为了看清楚栈的变化我们模拟一组数据输入7 1 2 2 1 3 3 4过程如下表步骤当前元素操作前栈操作操作后栈11[]入栈[1]22[1]2≠1入栈[1,2]32[1,2]22弹出栈顶[1]41[1]11弹出栈顶[]53[]入栈[3]63[3]33弹出栈顶[]74[]入栈[4]最终栈大小为 1剩余序列是 [4]。观察这里的关键点第 3 步弹出前一个 2 后栈变成 [1]第 4 步读取 1 时自然与栈顶 1 匹配并弹出。这就实现了“连锁消除”但全程没有任何回退扫描。3.4 另一种常见变体等价条件为“和为 0”如果题目定义为“两个相邻元素互为相反数时可以消除”只需要把equivalent函数改成inline bool equivalent(int x, int y) { return x y 0; }这里有个坑如果元素值可能很大比如绝对值达到 10^9那么x y可能会达到 2×10^9还在 int 范围内但如果题目给到 10^18 这种级别就必须用long long来存。七级认证通常不会给那么夸张的数据但仍要留个心眼。我也见过有人把equivalent写成x -y这和x y 0数学上等价但在某些情况下容易因为类型转换出问题。统一用加法判断语义更清晰。4. 常见问题排查与避坑实录写题解最怕“会做但拿不到分”。我根据自己带队的经验把同学们在这道题上踩过的坑整理成几个高频问题全部排查一遍基本就能满分。4.1 为什么我的答案总是多出几个元素多数情况是因为忽略了空栈判断导致第一个元素进栈后后面有些本该匹配的被错误入栈。比如栈为空时st.back()返回未定义值恰好可能和你当前元素相等结果鬼使神差地弹出了一个不存在的元素后续逻辑全乱。还有一种情况是等价条件写反了。比如题目要求“数值相等”你写成了 “绝对值相等”那么 [1, -1] 会被消除而正确做法中它们不该消。这类错误在样例弱的情况下很难暴露必须自己编一些反例来验证。排查手段很简单把最终栈内容输出出来人肉检查一遍不符合预期的位置。如果你不想手算可以在本地随机生成小数据用朴素模拟法做对拍。4.2 大数据下超时卡在哪里超时大概率是整体算法退化成了 O(n²)。常见写法是while (true) { bool flag false; for (int i 0; i 1 n; i) { if (a[i] a[i 1]) { a.erase(...); flag true; } } if (!flag) break; }这个写法在随机数据下可能表现还行但如果数据被构造为“每轮只能消一对然后连锁引发下一对”它就会退化得非常慢。举个典型例子[1, 2, 2, 3, 3, 1]第一轮消掉 [2,2]然后 3 和 3 还没有相邻第二轮才能消 [3,3]这样每一轮只消除一对总轮数接近 n/2。栈解法完全不会存在这个问题。另外如果数据规模 n 到 10^6vector频繁push_back也可能因为扩容造成少量时间损失所以记得reserve(n)。4.3 边界测试用例速查表我建议拿到题目后至少跑下面这些手写数据能快速帮你确认算法正确性测试数据期望结果说明n0空序列0需要确认题目是否允许空输入n1[7]1单元素必然无法消除[1,1]0两个相等元素直接消除[1,2,2,1]0连锁消除后为空[1,2,2,3,3,1]0分两轮完成消除[1,2,2,1,3]1最后剩 3[5,5,5]1前两个消掉剩下一个 5[5,5,5,5]0两两配对全部消除[1,2,3,4]4完全没有相邻相等跑完这些边界数据再跑一遍题目给出的样例基本能把 90% 的隐藏问题揪出来。4.4 本地构造数据的专用技巧很多同学不知道如何自己生成“棘手”数据。分享一个简单实用的方法写一个暴力的朴素函数专门处理小数据再写一个栈解法然后用随机生成器在本地做对拍。伪代码如下vectorint gen(int n) { vectorint a(n); for (auto x : a) x rand() % 5; // 小范围更容易出现相等 return a; } int brute(vectorint a) { // 复制一份 a不断扫描删除 bool changed true; while (changed) { changed false; for (int i 0; i 1 (int)a.size(); i) { if (a[i] a[i 1]) { a.erase(a.begin() i, a.begin() i 2); changed true; break; } } } return (int)a.size(); }对拍时生成 n 从 1 到 12 的小数据比较暴力解和栈解的输出。只要跑上几百组逻辑错误基本无处遁形。这个方法不仅适用于这一道题也适用于大多数模拟类算法题。5. 从这道题延伸出去等价消除还能怎么变一道题如果只背代码价值就浪费了大半。把“等价消除”理解透之后你会发现它背后是一大类“栈匹配”问题。5.1 把“相等”推广为“函数等价”等价消除的核心框架非常统一if (!st.empty() f(st.back(), x)) { st.pop_back(); } else { st.push_back(x); }唯一的区别就是f的定义等价条件函数写法注意点数值相等x y最常见互为相反数x y 0大数需开 long long异或和为固定值 k(x ^ y) k注意优先级加括号乘积为固定值 k1LL * x * y k乘积可能爆 int同余于某个 modx % mod y % mod注意负数取模理解了这个统一性以后见到“相邻两个元素满足 xx 就消除”的题你甚至不需要重新分析直接套框架改函数就行。5.2 当“消除段价值”要求最大化时就不是简单栈如果题目从“求最终长度”变成“求最多能消除多少次”或者“消除两个数能获得分数求最大分数”那栈就不一定是最优解了可能需要区间 DP、贪心加大根堆、甚至线段树优化。举个常见的升级版本每次消除相邻两个数得到它们乘积的分数求最大总分数。这种题就要用区间 DP 或者更复杂的策略去解决。七级认证不太会考到那么深但如果你准备后续更高级别建议把区间 DP 里的“括号消除模型”也一起复习。它们和等价消除的关系非常近核心都是从“相邻消除”出发只是决策方式不同。5.3 七级考试常见的配套知识点从这道题能牵出一份复习清单栈、队列、链表模拟、双指针、哈希表、前缀和、排序。实际考试中栈经常和括号匹配、表达式求值、单调栈结合出现。等价消除正是“匹配类”题型里最有代表性的一个。我在准备这类题时会额外训练自己拿到题目先看数据范围再想有没有“进入顺序决定后续关系”的性质最后再落笔写代码。等价消除这套路一旦熟练处理括号匹配、HTML 标签配对、HTML 标签有效性等类似问题时都会顺手很多。最后分享个人实操中的一个小习惯。我在客户端答题时写完代码不会立刻提交而是先构造五组手工数据空序列、单元素、全相同偶数组、完全消除样例、连环消除样例。跑完之后再随机对拍一轮暴力解确认无误再提交。很多人觉得这样耽误时间但省下的却是无数次罚时重交。这道“等价消除”对我印象最深的地方不是算法本身有多难而是它完美演示了“一个简单数据结构如何把一个看起来要反复扫描的问题变成一趟线性扫描”。比赛里真正拉开差距的往往就是这种建模敏感度。