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++实现：

#include<bits/stdc++.h> using namespace std; int main() { vector<vector<int>> res; // 存储所有完成的宝塔 vector<int> a, b; // a模拟A柱，b模拟B柱 int n; cin >> n; while(n--) { int x; cin >> x; if(a.empty()) { a.push_back(x); // 规则3：A柱为空时直接放入 } 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; }

关键操作点详解

成品保存机制：
- 使用vector<vector<int>> res存储所有完成的宝塔
- 每当需要重置A柱时，将当前a向量存入res
- 最后处理剩余未完成的a和b
B栈元素转移：
```
while(!b.empty() && b.back() > x) { a.push_back(b.back()); b.pop_back(); }
```
- 这个循环确保只转移B栈中大于当前彩虹圈直径的元素
- 保持转移后A栈依然满足从大到小的顺序
边界条件处理：
- 初始空栈处理
- 最终剩余栈处理
- 空输入处理（虽然题目保证N≥1）

3. 实例推演与状态转换

让我们用题目给出的样例进行逐步推演，直观理解双栈如何协同工作：

输入样例：

11 10 8 9 5 12 11 4 3 1 9 15

推演过程：

步骤	当前彩虹圈	A柱状态	B柱状态	操作说明
1	10	[10]	[]	初始放入A柱
2	8	[10,8]	[]	8<10，直接放入A
3	9	[10]	[9]	9>8，B为空，放入B
4	5	[10,5]	[9]	5<9不成立，5<10，直接放入A
5	12	[12]	[9]	12>10，保存A=[10,5]，转移B>12无，放入A
6	11	[12,11]	[9]	11<12，直接放入A
7	4	[12,11,4]	[9]	4<11，直接放入A
8	3	[12,11,4,3]	[9]	3<4，直接放入A
9	1	[12,11,4,3,1]	[9]	1<3，直接放入A
10	9	[9]	[]	9>1，保存A=[12,11,4,3,1]，转移B>9无，放入A
11	15	[15]	[9]	15>9，B为空，放入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, vector<int>& main_stack, vector<int>& temp_stack, vector<vector<int>>& 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)	括号匹配、表达式求值
需要维护某种单调性	单调栈	可以高效维护区间极值	每日温度、最大矩形面积
需要双向操作	双栈	可以模拟队列或提供更多灵活性	用栈实现队列、本题堆宝塔