实现删除堆栈的相邻编号，剩余多少

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

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

Answer 2

如果恒定内存空间至少为N，则朴素方法已经是线性的：(

也就是说，给定p=先前值(初始化为无穷大(和C=计数器(初始化为0(：

1. 弹出元素E
2. 如果E=P，则递增C，否则将C设置为1
3. 如果C>=3，继续弹出元素，覆盖E，关闭第二个堆栈，直到E=/=P
4. 将E推到第二个堆栈上
5. 从1开始重复，直到第一个堆栈为空，然后弹出并推送临时堆栈回到原来的，像您所做的那样为每个数字递增一个计数器