如何以最少移动次数完成多栈中同类物品的归位排序？

问题定义 #

• 给定n个容量为4的栈，p种物品（1 < p < n），每种物品恰好有4个，分散在各栈中
• 仅允许操作：弹出某栈栈顶物品，推入另一栈（目标栈可空或已有1-3个物品）
• 目标：用最少操作实现每个栈仅存放同类物品

核心优化策略 #

1. 优先填充"同类型半满栈" #

• 先遍历所有栈，标记出每种物品已存在且未满4个的栈
• 直接将栈顶的同类型物品推入对应栈，跳过临时存储环节，减少操作次数

2. 用空栈做临时缓冲区 #

• 当需要取出栈内部的目标物品时，先把栈顶的非目标物品临时存入空栈（或可清空的栈）
• 临时存储的物品要尽量一次性归位，避免反复移动增加操作次数

3. 按"埋藏深度"处理物品 #

• 对于每种物品，统计其在各栈中的位置：栈顶的物品无需移动，往下每深一层，需要多1次移动（先移走上方物品）
• 优先处理埋藏深度浅的物品，减少临时移动的总次数

示例实操（对应题目初始状态） #

初始状态：

• 栈1: A,B,B,A
• 栈2: A,B,A
• 栈3: B
• 栈4: 空

最优操作步骤（共7次）：

1. 弹出栈1栈顶的A，推入栈4
2. 弹出栈1栈顶的B，推入栈3（栈3变为B,B）
3. 弹出栈1栈顶的B，推入栈3（栈3变为B,B,B）
4. 弹出栈2栈顶的A，推入栈1（栈1变为A,A）
5. 弹出栈2栈顶的B，推入栈3（栈3变为B,B,B,B，完成B的归置）
6. 弹出栈2栈顶的A，推入栈1（栈1变为A,A,A）
7. 弹出栈4栈顶的A，推入栈1（栈1变为A,A,A,A，完成A的归置）

注意事项 #

• 非临时栈禁止混放不同类型物品，否则后续需要额外操作分离
• 每次操作前确认目标栈剩余容量≥1，避免违反栈的容量限制

内容的提问来源于stack exchange，提问作者Iulian Popa