自学TAOCP时对多栈溢出问题证明的困惑求助

我正在自学TAOCP，现在卡在了第2.2.2节（线性表：顺序分配）的问题[30]的证明上，想请大家帮忙理清楚思路。

问题背景 #

先把问题和相关定义明确一下：

• 设σ是任意的插入、删除操作序列，s₀(σ)是使用图4的简单方法，在初始条件(11)下执行σ时发生的栈溢出次数；s₁(σ)是在其他初始条件（比如(13)）下执行σ时的溢出次数。需要证明：s₀(σ) ≤ s₁(σ) + L∞ − L₀
• 初始条件(11)：对于1 ≤ j ≤ n，BASE[j] = TOP[j] = L₀，BASE[n+1] = L∞。也就是说，初始时所有空间（L∞ − L₀）都给了第n个栈，其他所有栈都是空的。
• s₁对应的初始条件可以是任意的，比如把所有空间平均分配给n个空栈。
• 溢出处理规则：当栈i溢出时，先找后续最近的未满栈，把内容“向上挪一格”；如果后续栈都满了，就找前面最近的未满栈，“向下挪一格”；如果完全找不到空间，就失败。

我的直观理解 #

能看出来，如果初始分配选得合理，一开始的很多栈溢出是可以避免的——比如不像(11)那样把所有空间都给最后一个栈。但不管初始分配多好，它最多只能减少固定次数的溢出，只有在程序运行早期才有明显效果。

官方提示的困惑 #

给出的提示是：

首先证明任何时刻都有BASE[j]₀ ≤ BASE[j]₁。然后观察：s₀(σ)中那些在s₁(σ)中没有发生的溢出，发生在栈i的规模达到了前所未有的大小，但此时它的新规模不超过s₁初始分配给栈i的大小。

但我觉得“前所未有的大小”这个说法不对啊！比如这种情况：栈i先满了，然后执行一次删除操作让它缩小，之后再插入一个元素导致溢出——这时候栈i是变大了，但并不是“比之前任何时候都大”。正因为这个点想不通，我完全get不到提示的意思，也不知道该怎么完成这个证明。

我现在的目标是证明s₀(σ)最多比s₁(σ)多L∞ − L₀次溢出，但目前完全卡壳了，有没有大佬能帮忙点拨一下？

备注：内容来源于stack exchange，提问作者Cam Miller