求两个动态栈中公共元素的最小重复数量算法实现

核心需求拆解 #

需要实现三个关键逻辑：遍历两个动态栈至栈底、统计每个栈内元素的出现次数、输出公共元素在两个栈中的最小出现次数。

1. 遍历栈至栈底并统计元素次数 #

由于栈是**后进先出（LIFO）**结构，要遍历到栈底需借助临时栈暂存元素（若需保留原栈结构），具体步骤：

• 为目标栈创建一个哈希表（或字典），用于存储元素与对应出现次数
• 初始化一个临时栈，用于存放遍历过程中弹出的元素
• 循环弹出原栈的栈顶元素：
  • 若元素已在哈希表中，计数+1；否则将元素加入哈希表并设计数为1
  • 将弹出的元素压入临时栈
• 遍历完成后，把临时栈的元素依次压回原栈，恢复原栈的初始结构

2. 计算公共元素的最小出现次数 #

• 拿到两个栈的元素计数哈希表后，遍历其中一个哈希表的所有元素
• 检查当前元素是否存在于另一个哈希表中
• 若存在，取两个哈希表中该元素计数的最小值，记录为该公共元素的结果

3. 结果输出 #

按照指定格式输出每个公共元素及其最小出现次数，示例格式：bread --> 3

伪代码示例 #

// 统计单个栈的元素出现次数，同时保留原栈结构
function countStackElements(stack):
    countMap = {}
    tempStack = []
    // 遍历栈并统计
    while stack is not empty:
        element = stack.pop()
        countMap[element] = countMap.get(element, 0) + 1
        tempStack.append(element)
    // 恢复原栈
    while tempStack is not empty:
        stack.append(tempStack.pop())
    return countMap

// 处理两个目标栈
stack1 = 输入的动态栈1
stack2 = 输入的动态栈2

counts1 = countStackElements(stack1)
counts2 = countStackElements(stack2)

// 输出公共元素的最小次数
for item in counts1:
    if item in counts2:
        min_count = min(counts1[item], counts2[item])
        print(f"{item} --> {min_count}")

关键说明 #

• 若无需保留原栈结构，可以省略临时栈恢复原栈的步骤，进一步简化逻辑
• 哈希表的操作时间复杂度为O(1)，整体算法时间复杂度为O(n+m)（n、m分别为两个栈的元素总数）
• 只要动态栈支持pop()、push()、isEmpty()（或等价判断空的方法）这三个基础操作，该算法即可适配

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