Stack实现O(1)的Min和Max：从空间换时间到数学魔法的探究

Stack实现O(1)的Min和Max：从空间换时间到数学魔法的探究

March 1, 2018
Algorithm
Golang, Algorithm

栈（Stack）作为一种基础的数据结构，其 Push 和 Pop 操作的 $O(1)$ 时间复杂度通过栈顶指针即可轻松保证。但如果在实际业务场景或算法挑战中，要求我们实现 O(1) 时间复杂度内的 Min 和 Max 操作，问题就变得有趣起来了。

背景 #

在常规的栈实现中，如果我们需要获取栈内的最大值或最小值，通常的做法是遍历整个栈。这种做法的时间复杂度是 $O(N)$，其中 $N$ 是栈中元素的数量。

然而，在某些对性能要求苛刻的场景（如实时流监控窗口的最值计算）或者算法面试中，通常会要求我们将 Min 和 Max 的获取时间也压缩到 $O(1)$。

面对这个需求，我们最先想到的思路通常是“空间换时间”：即通过维护额外的状态来实时记录最值。那么，具体该如何设计并保证数据的一致性呢？

方案一：辅助栈 (Auxiliary Stack) #

最直观的思路是设置一个辅助结构来同步记录最值。我们以“最大值”为例，引入一个辅助栈 SMax。

算法描述 # 

State:
  DataStack: [Integer] // The primary storage
  SMax:      [Integer] // Auxiliary stack to store the sequence of maximums

在这个方案中，逻辑如下：

  • Push: 当元素入栈时，我们不仅将其压入数据栈；同时，比较该元素与 SMax 栈顶元素。如果该元素大于等于 SMax 栈顶元素（或者 SMax 为空），则将该元素也压入 SMax。
  • Pop: 当元素出栈时，判断该元素是否等于 SMax 的栈顶元素。如果相等，说明我们要弹出的正是当前的最大值，因此 SMax 也要同步弹出栈顶。

伪代码描述 # 

Function Push(element):
    DataStack.Push(element)
    // If element is new max, push to SMax
    IF SMax.IsEmpty() OR element >= SMax.Top():
        SMax.Push(element)

Function Pop():
    value = DataStack.Pop()
    // If we are popping the current max, pop from SMax too
    IF value == SMax.Top():
        SMax.Pop()
    RETURN value

Function GetMax():
    RETURN SMax.Top()

场景推演 #

为了验证这个逻辑，我们以序列 1, 3, 6, 1, 12, 512, 12, 5121, 121, 412 为例进行推演：

Step-1. 元素 1 入栈 当前 SMax 为空，直接入栈。

Stack: 1
SMax:  1

Step-2. 元素 3 入栈 3 > 1，为了保证 SMax 栈顶始终是当前最大值，3 入 SMax。

Stack: 1, 3
SMax:  1, 3

Step-3. 元素 6 入栈 6 > 3，同步更新。

Stack: 1, 3, 6
SMax:  1, 3, 6

… 省略中间步骤 …

Step-End. 所有元素入栈后 最终状态如下：

Stack: 1, 3, 6, 1, 12, 512, 12, 5121, 121, 412
SMax:  1, 3, 6, 12, 512, 5121

注：SMax 中仅存储比栈顶更大的新元素，因此 1, 12, 121, 412

可以看到，这种方式逻辑清晰，实现简单。但从推演中我们也发现了一个明显的缺陷：空间复杂度。

如果入栈的元素是递增序列（如 1, 2, 3, ... N），那么 SMax 栈的大小将等同于数据栈，空间耗费为 $2N$。仅仅为了记录一个最值，耗费了一倍的额外空间，这显然不是最优解。

方案二：差值标记法 (Value Difference) #

有没有一种方法，既能保证 $O(1)$ 的时间复杂度，又能显著减少空间占用？

回顾我们的需求，我们真正关心的是“当前的最大值”。如果我们利用栈中存储的元素本身来承载一些“额外信息”，是否可行？答案是肯定的，我们可以存储差值。

算法设计 #

在这个优化方案中，我们不再存储原始数值，而是存储 (当前元素 - 当前最大值) 的差值。

State:
  DataStack: [Integer] // Stores the difference (Val - Max)
  Max:       Integer   // Tracks the current maximum value

其核心逻辑显得略微“反直觉”，这里需要细细品味：

  • Push:
    • 计算 diff = 当前元素 - Max，将 diff 入栈。
    • 如果 当前元素 > Max，说明最大值变了，更新 Max = 当前元素。
    • (注意：此时栈顶存储的 diff 是正数，标记了新 Max 的产生)
  • Pop:
    • 取出 栈顶元素 (diff)。
    • 如果 diff > 0：说明在这个元素入栈时更新过 Max。当前实际弹出的元素就是 Max，而上一个 Max 的值可以通过 Max - diff 还原。我们需要更新 Max = Max - diff。
    • 如果 diff <= 0：说明入栈时比 Max 小，没更新过 Max。当前实际弹出的元素是 Max + diff，无需更新 Max。

伪代码描述 # 

Function Push(element):
    IF DataStack.IsEmpty():
        Max = element
        DataStack.Push(0) // 0 means element == Max
    ELSE:
        diff = element - Max
        DataStack.Push(diff)
        // If diff > 0, it means element > current Max
        IF diff > 0:
            Max = element

Function Pop():
    diff = DataStack.Pop()
    
    IF diff > 0:
        // This element updated the Max when pushed
        // Current value is Max, we need to restore previous Max
        value = Max
        Max = Max - diff
        RETURN value
    ELSE:
        // Max was not updated by this element
        // Original value was (Max + diff)
        RETURN Max + diff

Function GetMax():
    RETURN Max

深度复盘 #

这个逻辑比较抽象，我们用一组数据 5, 23, 12, 499, 45, 20, 60 来进行一次完整的“抓包”分析。

Step-1. 元素 5 入栈 当前 Max 初始化为极小值。 入栈内容：5 - MinInt (正数)。 更新 Max = 5。

Stack: [5-MinInt]
Max:   5

Step-2. 元素 23 入栈 当前元素 23 > Max(5)。 入栈内容：23 - 5 = 18。 更新 Max = 23。

Stack: [..., 18]
Max:   23

Step-3. 元素 12 入栈 当前元素 12 < Max(23)。 入栈内容：12 - 23 = -11。 不更新 Max。

Stack: [..., 18, -11]
Max:   23

此时，如果我们要进行 Pop 操作，流程如下：

Step-4. 弹出栈顶 -11 栈顶 -11 < 0。 这意味着当前 Max 并不是在这个元素入栈时被修改的。 还原真实元素：Max(23) + (-11) = 12。 Max 保持 23 不变。

Stack: [..., 18]
Max:   23

结果正确：弹出了 12，且 Max 仍为 23。

Step-5. 弹出栈顶 18 栈顶 18 > 0。 这是一个关键信号！说明当初这个元素入栈时，它推高了 Max 值。 当前真实元素就是 Max(23)。 我们需要“回溯” Max 值：NewMax = Max(23) - 18 = 5。

Stack: [...]
Max:   5

结果正确：弹出了 23，且 Max 恢复为了 5。

优势分析 #

相较于辅助栈方案，差值法的优势在于：

  1. 空间效率：不需要额外的 $O(N)$ 空间存储辅助栈，仅需 $O(1)$ 的变量存储 Max。
  2. 优雅性：利用数学特性（加减逆运算）还原上下文，减少了数据结构的复杂度。

举一反三：最小值的实现 #

上述逻辑着重探究了 Max 的实现，对于 Min 的实现，原理是完全对称的。

对于辅助栈法，我们只需要维护一个 SMin 栈，Push 时若当前元素 <= SMin 栈顶则入栈，Pop 时若等于则出栈。

对于差值标记法，逻辑稍作调整：

  • Push: 存储 当前元素 - Min。若 当前元素 < Min，则更新 Min。此时入栈的差值为负数。
  • Pop: 若 栈顶元素 < 0，说明更新过 Min，还原 PreMin = Min - 栈顶元素。

总结 #

本文从一个简单的 $O(1)$ 最值需求出发，展示了两种截然不同的解决思路。

  • 辅助栈法胜在直观、易理解，符合线性思维，但在极端情况下空间浪费严重。
  • 差值标记法利用了数据的相对关系，通过数学变换将“历史状态”编码在当前数据中，实现了极致的空间优化。

在实际工程和算法设计中，这种“利用数据间的相对关系来压缩信息”的思想（类似差分数组、前缀和）是非常通用的解题利器。知其然更知其所以然，才能在面对更复杂的问题时游刃有余。

访问量 访客数