PTA L2-045 堆宝塔题解：用两个栈模拟游戏过程，保姆级图解+代码逐行分析

PTA L2-045 堆宝塔双栈模拟的艺术与实战拆解当彩虹圈遇上数据结构一场关于栈的思维体操就此展开。这道PTA天梯赛L2级别的题目表面上是儿童游戏模拟实则是数据结构应用的绝佳案例。我们将从游戏规则解析入手逐步拆解如何用两个栈或向量完美模拟堆宝塔的全过程。1. 游戏规则与数据结构映射堆宝塔游戏的核心在于两根柱子的协同操作——这正是栈结构后进先出特性的完美体现。让我们先理清题目描述的每一个动作对应的数据结构操作A柱主栈用于构建当前正在堆叠的宝塔。每次只能从顶部添加或移除彩虹圈完全符合栈的特性。B柱辅助栈用于临时存放不符合当前主栈条件的彩虹圈。当主栈需要重置时B柱中的部分元素会转移回A柱。游戏的关键操作流程可以抽象为以下步骤初始化两个空栈A和B读取下一个彩虹圈直径C如果A为空直接将C压入A栈否则比较C与A栈顶元素如果C更小压入A栈否则检查B栈如果B为空或C大于B栈顶压入B栈否则将当前A栈作为成品保存清空A栈将B栈中所有大于C的元素转移到A栈最后将C压入A栈重复2-4直到所有彩虹圈处理完毕将剩余的A栈和B栈如有作为最终成品2. 代码实现逐行解析让我们深入分析参考代码的每一部分理解如何将上述逻辑转化为C实现#includebits/stdc.h using namespace std; int main() { vectorvectorint res; // 存储所有完成的宝塔 vectorint a, b; // a模拟A柱b模拟B柱 int n; cin n; while(n--) { int x; cin x; if(a.empty()) { a.push_back(x); // 规则3A柱为空时直接放入 } else if(x a.back()) { a.push_back(x); // 规则4a比A栈顶小直接压入 } else if(b.empty() || x b.back()) { b.push_back(x); // 规则4b符合B柱条件时压入B栈 } else { res.push_back(a); // 保存当前A栈为成品 a.clear(); // 清空A栈准备重建 // 转移B栈中大于x的元素到A栈 while(!b.empty() b.back() x) { a.push_back(b.back()); b.pop_back(); } a.push_back(x); // 最后压入当前彩虹圈 } } // 处理最后剩余的宝塔 if(!a.empty()) res.push_back(a); if(!b.empty()) res.push_back(b); // 计算最大层数 int mx 0; for(auto c : res) { mx max(mx, (int)c.size()); } cout (int)res.size() mx; return 0; }关键操作点详解成品保存机制使用vectorvectorint res存储所有完成的宝塔每当需要重置A柱时将当前a向量存入res最后处理剩余未完成的a和bB栈元素转移while(!b.empty() b.back() x) { a.push_back(b.back()); b.pop_back(); }这个循环确保只转移B栈中大于当前彩虹圈直径的元素保持转移后A栈依然满足从大到小的顺序边界条件处理初始空栈处理最终剩余栈处理空输入处理虽然题目保证N≥13. 实例推演与状态转换让我们用题目给出的样例进行逐步推演直观理解双栈如何协同工作输入样例11 10 8 9 5 12 11 4 3 1 9 15推演过程步骤当前彩虹圈A柱状态B柱状态操作说明110[10][]初始放入A柱28[10,8][]810直接放入A39[10][9]98B为空放入B45[10,5][9]59不成立510直接放入A512[12][9]1210保存A[10,5]转移B12无放入A611[12,11][9]1112直接放入A74[12,11,4][9]411直接放入A83[12,11,4,3][9]34直接放入A91[12,11,4,3,1][9]13直接放入A109[9][]91保存A[12,11,4,3,1]转移B9无放入A1115[15][9]159B为空放入B最终处理保存A[15]为成品将B[9]转为宝塔[9]保存成品宝塔[10,5][12,11,4,3,1][15][9]4. 算法优化与边界思考虽然题目给出的数据规模(N≤1000)使得O(N²)的解法完全可行但我们仍可以思考可能的优化空间和边界情况时间复杂度分析每个元素最多被压入和弹出各两次A栈和B栈整体时间复杂度为O(N)最坏情况下如完全逆序输入会频繁触发宝塔保存操作空间复杂度使用两个栈存储当前元素O(N)空间结果存储所有宝塔最坏情况下O(N)空间易错点警示初始条件检查忘记处理第一个元素的特殊情况栈空判断在访问栈顶元素前未检查栈是否为空元素转移条件错误地将B栈中所有元素而非仅大于当前值的元素转移最终处理遗漏处理循环结束后A栈和B栈中剩余的元素代码可读性优化使用更具描述性的变量名如main_stack/temp_stack将核心逻辑封装为独立函数添加注释说明关键决策点// 优化后的函数封装版本 void process_rainbow_ring(int x, vectorint main_stack, vectorint temp_stack, vectorvectorint result) { if(main_stack.empty()) { main_stack.push_back(x); } else if(x main_stack.back()) { main_stack.push_back(x); } else if(temp_stack.empty() || x temp_stack.back()) { temp_stack.push_back(x); } else { result.push_back(main_stack); main_stack.clear(); while(!temp_stack.empty() temp_stack.back() x) { main_stack.push_back(temp_stack.back()); temp_stack.pop_back(); } main_stack.push_back(x); } }5. 栈结构在算法题中的常见应用模式通过这道题我们可以总结栈在算法问题中的几种典型应用场景模拟系统如本题模拟物理堆叠过程浏览器前进后退功能文本编辑器的撤销重做括号匹配检查表达式中的括号是否合法嵌套计算嵌套深度单调栈解决下一个更大元素类问题柱状图最大矩形面积计算函数调用栈程序执行时的函数调用关系递归函数的非递归实现栈选择技巧对比表场景特征适用数据结构原因典型例题后进先出的物理过程栈天然匹配操作顺序堆宝塔、汉诺塔需要频繁访问最近元素栈直接访问栈顶O(1)括号匹配、表达式求值需要维护某种单调性单调栈可以高效维护区间极值每日温度、最大矩形面积需要双向操作双栈可以模拟队列或提供更多灵活性用栈实现队列、本题堆宝塔掌握栈的这种后进先出特性能够帮助我们更自然地模拟许多现实世界的过程。在解决算法问题时当遇到以下关键词时就可以考虑栈是否适用最近匹配、嵌套结构、撤销操作、分层处理、顺序反转等回到本题堆宝塔游戏完美展现了如何用栈来模拟具有明确顺序约束的物理过程。通过A、B双栈的协同我们能够高效地管理彩虹圈的暂存和转移这正是数据结构抽象现实问题的魅力所在。