然后我们说明不存在均摊低于 \Theta(\log n) 次 pop 的做法。我们考虑这样一个弱化的问题:初始时栈内有 n 个 0,做 n 次操作,每次删除一个 0,加入一个 1。设解决这个问题所需的最小 pop 次数为 T(n)。由于所有的 0 都被删掉了,必然有一次操作把整个栈的元素全部 pop 了出来(否则最下面的 0 不可能出栈),设这次操作为第 k 次。那么我们删除前 k-1 个元素至少用 T(k-1) 次 pop(因为无视对前 k-1 次没删掉的元素的 pop/push 就能规约到规模 k-1 的问题),第 k 次操作用 n 次 pop,后 n-k 次操作至少用 T(n-k) 次 pop(无视掉对新加入的 k 个元素的 pop/push)。于是 T(n) \geq \min_{1 \leq k \leq n} \{T(k-1)+T(n-k)+n\}。注意到这个式子就像是求一个二叉树的子树大小和,而这等于所有节点的深度和(根的深度为 1)。至少有 \lceil n/2 \rceil 个点深度 \geq\lfloor\log_2 n\rfloor,于是 T(n)=\Omega(n \log n)。
所以我们可以预期一个均摊 \Theta(\log n) 的做法。
我们先考虑给出一个弱化版的 \Theta(n\log n) 做法。很明显可以把大小为 n 的完全二叉树建出来,每个节点以中序遍历的顺序对应最开始从栈顶到栈底的 0。中序遍历整个二叉树,对于每个点 x,遍历完 x 的左子树后,把栈顶的 x 的子树大小个元素 pop 出来,按原顺序把所有 1 塞到下面,所有 0 放在栈顶,然后 pop 0 并 push 1,继续中序遍历右子树。根据之前的分析,这样我们会 pop \Theta(n \log n) 次。push 次数和 pop 是同阶的,所以总时间复杂度 \Theta(n \log n)。
当然实际上可能不止加入了 n 个 1。我们只需要稍作修改,把「pop 出栈顶的子树大小个元素」改成「不断 pop 栈顶直到 pop 出右子树大小 +1 个 0」就可以了。现在我们说明这种做法仍能保证时间复杂度的正确性。假设我们加入了 m 个 1,之前的论证仍能说明 0 只被 pop/push 了 \Theta(n \log n) 次,那 1 呢?观察到如果我们在中序遍历 x 时 pop 了某个 1,那么它在 x 的子树遍历完成之前都不会再动了。所以每个 1 最多被 pop 树高次,总次数是 \Theta(m \log n) 的。总时间复杂度为 \Theta(m \log n)。