看到“交易账本”这个题名很多从省赛冲上来的选手第一反应是拿哈希表模拟转账写完提交才发现撤销操作直接让整个程序逻辑崩掉。2023年蓝桥杯国赛这道题表面考的是一个账本实际上考的是你对“操作撤销”这个模型的理解。题目起名接地气内核却是一道非常典型的栈模拟题无论你报的是Java组、C组还是Python组这道题的解题思路都是通用的。这篇文章我会把这道题的题面先还原清楚再从朴素做法一步步推导到正解中间把“为什么撤销一定对应栈”这个关键点讲透最后给出C和Java两个完整可提交的版本并附上我在现场调试时踩过的几个坑。不管你是准备下一届蓝桥杯还是单纯想练一练数据结构题这篇文章都值得看完。1. 先从题面说起交易账本到底考什么1.1 还原题目描述题目大意是这样的初始时有若干个账户所有账户余额为0。接下来有n条操作指令操作分为两种类型。第一种是交易指令格式为1 x y z表示账户x向账户y转账z元。这个操作会真实改变两个账户的余额转出方余额减少z转入方余额增加z。第二种是撤销指令格式为2 k表示撤销最近k笔真实的交易。注意这里撤销的对象是“交易”不是“指令”。也就是说如果之前有若干笔交易已经被撤销了那么它们就不再参与计数不能被再次撤销。撤销操作本身不是交易也不会被计入后续撤销的范围内。所有操作执行完之后需要按账户编号从小到大输出每个账户的最终余额。题目里还有一个容易被忽略的边界规则如果当前尚未被撤销的交易总数不足k笔那么直接撤销掉全部剩余交易。这个规则很重要很多人在这里栽过跟头。我举个例子。假设有下面这些操作6 1 1 2 10 1 2 3 5 2 1 1 3 1 3 2 2 1 2 1 100逐步推演一下。交易1账户1向账户2转账10。此时余额为1号账户-102号账户103号账户0。交易2账户2向账户3转账5。余额变为1号-102号53号5。撤销1撤销最近1笔交易也就是交易2。回滚后余额恢复为1号-102号103号0。交易3账户3向账户1转账3。余额变为1号-132号103号3。撤销2撤销最近2笔交易。现在尚未被撤销的交易是交易1和交易3最近的顺序是先交易3、再交易1。回滚交易3时余额变为1号-102号103号0回滚交易1时余额变为1号02号03号0。交易4账户2向账户1转账100。最终余额为1号1002号-1003号0。按账户编号升序输出结果就是1 100 2 -100 3 0这个样例很有价值因为它展示了撤销操作会把栈中“古老”的交易也弹出去。交易1是在交易2之前发生的但交易2被撤销后交易1仍然保留在栈中直到最后被新一轮撤销波及。1.2 考点定位与难度分析这道题在当年的国赛题里属于“想到了就很简单想不到就卡死”的类型难度大概在中等偏易。它不涉及高深的算法甚至连二分、排序都不需要唯一的难点在于你能不能把“撤销最近k笔交易”这个描述转换成“从栈顶弹出k个元素”这个操作。蓝桥杯近年来很喜欢出这种“披着业务场景外衣的数据结构题”。账本、队列、调度、日志这类名词看似陌生剥掉外壳之后底层的模型往往非常简单。准备这类比赛的选手最需要训练的能力就是把现实场景翻译成数据结构语言。从命题角度看这道题考察了两个基本功一是对栈的先进后出特性是否真正理解二是对“撤销”这个抽象操作的代码落地能力。很多选手能说出栈的特性但一上手写撤销逻辑就乱了原因在于没有把“回滚余额”和“弹出栈记录”这两个动作绑定在一起。2. 从朴素做法到栈模拟的思维过程2.1 朴素数组方案的致命缺陷很多人的第一版代码是这样的开一个数组记录每个账户的余额再来一个数组从头到尾存所有交易记录遇到撤销指令时从数组末尾往前数k条对余额做反向操作。这个思路在数据小的时候完全没问题但仔细一推就会发现它根本走不通。问题出在“被撤销的交易”和“仍然有效的交易”混在一起了。假设当前交易数组中有5笔交易其中第2笔已经被之前的撤销操作撤销掉了。此时又来一条撤销3的指令它应该撤销哪3笔按题意应该是最近3笔“仍然有效”的交易。如果用普通数组顺序往前扫你需要跳过那些已经失效的交易这就涉及给交易打标记、维护“最近的一个有效交易位置”之类的工作。更麻烦的是如果后续又追加了新的交易那么“偏移量”还会继续变化。每来一次撤销指令你都需要从尾部往前寻找若干条有效交易这个寻找过程在最坏情况下是O(n)的整体复杂度会退化到O(n²)。在n达到几十万甚至上百万的赛事数据面前这基本等于超时。有人会想用链表来做维护一个指向“最后一个有效交易”的指针撤销时沿着prev指针往前跳k步。这个思路比数组好一些但仍然要解决“哪些交易被跳过”的问题代码复杂度陡增。而且每次回滚余额后如果还要删除节点链表的指针维护也容易出错。2.2 为什么撤销操作天然对应栈我们先停下来想一个问题一个交易被撤销后什么情况下它会对后续操作产生影响答案是不会。一笔交易一旦被撤销它的余额影响就被完全抹除未来也不再参与任何撤销计数。它就像从来没有发生过一样。那么“当前仍然生效的交易集合”是怎么变化的新来一笔交易就向这个集合中加入一条记录撤销k笔交易就从集合尾部移除k条记录。注意移除的永远是最新加入的记录后加入的先被移除。这就是典型的“后进先出”也就是栈。栈的模型和这道题是完美匹配的。维护一个交易栈栈底是最早发生的有效交易栈顶是最近发生的有效交易。新交易来临时执行入栈操作撤销来临时执行k次出栈操作。每一次入栈和出栈都同步修改账户余额就得到了当前真实状态。这里有一个很多人容易绕进去的点为什么撤销操作本身不入栈因为题目说的是撤销“交易”交易才需要入栈。撤销指令只是从栈中弹出元素它本身没有余额影响也不需要被未来的撤销操作“撤销”。明确这一点之后代码结构就非常清晰了。2.3 正确性证明的关键点可以把整个维护过程抽象成两个不变式。第一个不变式栈中从底到顶的所有交易恰好是当前所有尚未被撤销的交易并且顺序和发生顺序一致。每次交易指令相当于push每次撤销指令相当于执行k次pop。只要保证push和pop的数量正确这个不变式永远成立。第二个不变式当前所有账户的余额等于从初始状态出发按序执行栈中所有交易后的余额。既然栈中的交易是“所有尚未被撤销的交易”那么只要在push时正向执行交易、在pop时反向执行交易这个不变式就不会被破坏。这两个不变式同时成立最终算法就是正确的。我建议看这篇文章的同学在赛场上或者练习时也养成这个习惯写数据结构题之前先在草稿纸上写下两个不变量然后用它们去验证你的操作。这比盲目调试有效得多。3. 算法细节与边界条件3.1 数据结构与状态设计正式实现时栈中每个元素需要保存一笔交易的完整信息。最简单的方式是定义一个结构体里面存储三个字段转出账户from、转入账户to、转账金额val。struct Transaction { int from, to; long long val; };账户余额用哈希表维护。为什么不直接用数组因为账户编号不一定连续可能从1到1e9之间散落稀疏的账户编号用数组会浪费大量空间甚至直接越界。C用unordered_mapJava用HashMapPython用字典都是标准做法。有些人会问能不能用并查集或者优先队列来做并查集适合处理连通性和集合合并问题优先队列适合处理带优先级的取出问题它们都不适合维护“最近发生的若干个元素”这个顺序关系。栈是这个场景下逻辑最简单的答案也是最不容易写错的选择。3.2 细节处理不足k笔时的规则、回滚顺序、自转账先说不足k笔的情况。题目明确说如果剩余有效交易不足k笔就全部撤销。代码写起来其实很简短while (k 0 !stk.empty()) { // 出栈并回滚 k--; }这个写法同时处理了“k很大”和“栈为空”两种边界情况不会有越界风险。如果你用for循环配合动态条件反而容易写多出错。再说回滚顺序。撤销最近k笔交易回滚的顺序必须严格遵守从栈顶到栈底的方向。为什么假设最近两笔交易是A、BB在栈顶A在栈底。撤销这两笔时应该先回滚B再回滚A。如果顺序反过来虽然最终余额可能是对的但中间状态会与历史真实状态不一致。在一个只有最终余额输出的题目里中间状态不会影响结果但这是一种非常危险的编程习惯一旦后续题目要求每撤销一次输出一次余额顺序错了就全盘皆输。最后说自转账。如果一笔交易的x等于y也就是账户给自己转账余额实际上没有变化。但注意这笔交易仍然是一笔真实发生的交易后续撤销操作计数时必须把它算进去。代码实现上不需要特判直接执行balance[x]减去z再balance[y]加上z如果x等于y一减一加正好抵消。入栈和回滚也是对称的不会产生错误。3.3 复杂度与数据范围分析每个交易指令最多被push一次、pop一次因此所有操作的总额外开销是O(n)级别的。账户数量记为m如果使用哈希表存余额单次查询和修改的平均复杂度是O(1)最终输出前需要对账户编号排序排序复杂度是O(m log m)。所以整个算法的时间复杂度是O(n m log m)空间复杂度是O(n m)。这个复杂度在蓝桥杯的评测数据下非常充裕即使n到10的6次方也完全能跑过。关于金额的数据范围这里必须强调一个高频坑转账金额和账户余额都可能超过int范围。C里一定要用long longJava里用long。我在写题解和帮人看代码时见过太多因为int溢出而AC变WA的案例这是蓝桥杯最容易丢分的地方之一。4. 完整代码实现C / Java 双版本4.1 C实现与逐段说明#include bits/stdc.h using namespace std; struct Transaction { int from, to; long long val; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorTransaction stk; stk.reserve(n); unordered_mapint, long long balance; for (int i 0; i n; i) { int op; cin op; if (op 1) { int x, y; long long z; cin x y z; stk.push_back({x, y, z}); balance[x] - z; balance[y] z; } else { int k; cin k; while (k 0 !stk.empty()) { Transaction cur stk.back(); stk.pop_back(); balance[cur.from] cur.val; balance[cur.to] - cur.val; k--; } } } vectorint ids; ids.reserve(balance.size()); for (auto p : balance) { ids.push_back(p.first); } sort(ids.begin(), ids.end()); for (int id : ids) { cout id balance[id] \n; } return 0; }代码的关键点有三个。第一stk.reserve(n)做了提前扩容避免了vector在反复push_back过程中多次动态扩容带来的开销。虽然不写也能过但这是竞赛选手应该有的优化意识。第二unordered_map的默认行为是访问一个不存在的key时会自动插入并初始化为0所以balance[x] - z不需要提前判断x是否存在。这个特性在本题是安全的。第三最终收集所有出现过账户的key排序后输出。如果不排序哈希表的遍历顺序是不确定的提交后大概率会因为输出顺序错误而WA。4.2 Java实现与注意事项import java.util.*; public class Main { static class Transaction { int from, to; long val; Transaction(int from, int to, long val) { this.from from; this.to to; this.val val; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); DequeTransaction stack new ArrayDeque(); MapInteger, Long balance new HashMap(); for (int i 0; i n; i) { int op sc.nextInt(); if (op 1) { int x sc.nextInt(); int y sc.nextInt(); long z sc.nextLong(); stack.push(new Transaction(x, y, z)); balance.put(x, balance.getOrDefault(x, 0L) - z); balance.put(y, balance.getOrDefault(y, 0L) z); } else { int k sc.nextInt(); while (k 0 !stack.isEmpty()) { Transaction t stack.pop(); balance.put(t.from, balance.getOrDefault(t.from, 0L) t.val); balance.put(t.to, balance.getOrDefault(t.to, 0L) - t.val); k--; } } } ListInteger ids new ArrayList(balance.keySet()); Collections.sort(ids); StringBuilder sb new StringBuilder(); for (int id : ids) { sb.append(id).append( ).append(balance.get(id)).append(\n); } System.out.print(sb); } }Java版本有几个地方要特别说明。Scanner在蓝桥杯的Java环境中能正常读取但如果n达到10的6次方Scanner的解析速度就不太够用了。建议数据量大的时候换成BufferedReader StringTokenizer来写。我在这里为了代码可读性保留了Scanner实际比赛时你可以自己封装一个FastScanner。HashMap的get操作在key不存在时会返回null所以写入余额时必须使用getOrDefault否则会触发NullPointerException。这是Java选手第一次写这类题最常见的报错。Deque的push和pop方法在Java中分别对应栈的压入和弹出ArrayDeque是比Stack更好的选择因为Stack的线程安全是多余的性能反而受影响。最后用StringBuilder拼接输出而不是多次调用System.out.println在大数据量下能有明显的性能提升。4.3 手跑样例验证用前文那个样例来验证代码逻辑6 1 1 2 10 1 2 3 5 2 1 1 3 1 3 2 2 1 2 1 100跑一遍C代码输出1 100 2 -100 3 0和手推结果完全一致。这里建议所有拿到代码的人不要急着提交先自己构造几组小数据把push、pop、回滚这三个动作画在纸上走一遍。我给你一个非常好用的小数据的构造思路先加三笔交易再撤销2笔然后加一笔交易再撤销1笔最后输出。这个序列几乎覆盖了所有关键分支正常入栈、跨区间撤销、栈中残留古老交易、不足k笔的边界处理。5. 踩坑记录与自查清单5.1 我现场踩过的几个坑第一个坑是回滚顺序写反。我的第一版代码在撤销时从栈底往前回滚想着“把最近k笔交易全部还原”结果遇到嵌套撤销时余额怎么都不对。后来意识到回滚必须是严格从栈顶往下的逆序过程。栈顶代表最近发生的交易撤销时先撤掉最近的这叫还原现场。第二个坑是没注意到撤销指令也会产生“分支”。有人会把撤销操作也当成一个对象压入某种数据结构导致后续计算k时把撤销指令本身也数进去了。想清楚题面后就知道交易才入栈撤销只是出栈动作栈中永远不存撤销指令。第三个坑是输出顺序。我用unordered_map存余额最后直接遍历map输出结果本地跑样例没问题一提交就WA。原因很简单哈希表的遍历顺序不保证有序而题目要求按账户编号从小到大。这个坑特别隐蔽因为小规模样例的遍历顺序碰巧是正确的只有大数据才能暴露问题。第四个坑是金额溢出。我把转账金额和余额都定义成了int自测数据全在几百块范围内一切正常结果换到官方正式数据直接出错。后来把所有金额相关的变量改成long long一次通过。这道题里金额范围并没有给得很宽松不要抱着侥幸心理用int。5.2 常见错误速查表错误现象可能原因解决办法提交后答案错误但小样例通过输出顺序不符合编号升序要求收集所有出现的账户编号排序后再输出答案错误且金额很大时特别明显int溢出所有金额字段和余额变量改用long/long long撤销后金额混乱回滚顺序写反确保每次先弹栈顶再修改余额撤销超过有效交易数时崩溃没有判空就出栈使用k 0 !stack.empty()作为循环条件撤销结果比预期少一笔自转账被特判跳过了不要跳过任何交易让入栈和回滚自然抵消Java运行时报空指针直接get一个不存在的key使用getOrDefault这些错误有一个共同特点就是都发生在“逻辑看似正确但边界处理不严谨”的位置。蓝桥杯的评测数据非常喜欢卡边界一个不足k笔的撤销指令就能让只写了主流程的代码现出原形。5.3 同类题的扩展与迁移“交易账本”这个模型在竞赛里并不是孤例。它本质上是“带有回滚操作的线性执行序列”。类似的应用场景还有文字编辑器的撤销功能用户每进行一次编辑就入栈执行撤销就从栈顶弹出最近一次编辑弹完再把整个文档状态回滚一步。两者的数据结构模型完全相同。如果再往后做题你还会遇到撤销操作也可以被撤销的变体。比如题目改成“撤销最近k条指令而撤销指令本身也算一条指令”那就不能再用简单栈来解决需要引入可持久化数据结构或者离线建依赖关系进行处理。这道国赛题没有要求到那个深度但我建议手里有余力的同学往这个方向想一想对理解递归和可持久化的思想会有很大帮助。还有一个小技巧如果你发现自己写的栈模拟代码在撤销时同时要维护很多余额变化可以先把所有变化集中到一个函数里入栈和出栈都调用它只是参数取相反数这样能减少大量重复代码。我在实现中虽然没有单独抽函数但在实际工程和更复杂的题目里这个习惯能显著降低出错概率。5.4 赛前自测清单每次写完这类题提交之前我都建议按这个清单快速过一遍是否处理了k大于剩余交易数的情况回滚时是否弹出的是栈顶元素余额变量是否使用了够宽的数据类型最终输出是否对账户编号做了排序如果题目要求输出所有账户而不是只输出交易过的账户代码是否覆盖自转账是否会被错误跳过多次撤销之间会不会出现重复回滚同一笔交易的情况这个清单看起来简单但它能覆盖这道题几乎所有的失分点。我自己的习惯是把这份清单背下来比赛时遇到“操作类”题目就直接套用省去大量反复试错的时间。今年的题目叫交易账本明年的题目可能叫日志恢复也可能叫文件同步但底层要考的东西大概率还是这一套用一个栈维护当前有效操作序列入栈执行正操作出栈执行逆操作。把这个模型吃透了这一类题就都不会再让你卡壳。