algorithm - 实现 去掉一个栈中相邻的数，还剩多少？

Question

假设我们有一个包含 n 个数字的堆栈，如果 3 个或更多相邻数字相等，则可以删除这些数字(从上到下删除数字)。由于这是一个堆栈，我们有正常的 push()、pop()、top() 操作并且我们知道 n。此外，我有一个空堆栈和 O(1) 额外的内存空间。是否有用于查找剩余数字数量的线性算法？如果是，那会是什么？

Answer 1

这个想法很简单。我们只需将条目移动到另一个堆栈并计算我们将删除的数量。为此，我们跟踪最后一个元素以及我们看到它的次数:

lastElement = ∅      //no last element
lastElementSeen = 0  //how many times did the last element occur in succession
totalRemoved = 0     //how many elements would we remove?
while(!stack.empty)
    element = stack.top
    stack.pop()
    otherStack.push(element)
    if element == lastElement
        lastElementSeen++
    else
        if lastElementSeen >= 3
            totalRemoved += lastElementSeen
        lastElement = element
        lastElementSeen = 1

您还可以选择从其他堆栈中实际移除元素，而不是仅仅对它们进行计数。如果您不再需要它们，您也可以选择不将它们放在另一个堆栈中。