algorithm - 如何定义一个可以在 O(1) 内获得最小数字的堆栈

Question

我在网上看到一道算法题，上面写着:

定义一个栈，包括一个min函数，通过min我们可以得到栈中最小的数 ，pop、push和min的时间复杂度都是O(1)。

我知道pop和push的复杂度是O(1)，但我不知道如何制作 min 复杂度也是 O(1)，如果我定义一个变量来记住每次 push 时的最小数字，但是当 pop，最小的数字可能会改变，所以我应该找到第二小的数字，这意味着 pop 复杂度不能是 O(1)。

那么stack应该怎么定义才能满足要求呢？

Answer 1

只需要另一个具有最小值的堆栈。当您将一个值压入您的常规堆栈时，将一个值压入您的最小堆栈。当您从常规堆栈中弹出一个值时，从您的最小堆栈中弹出一个值。您压入最小堆栈的值将只是当前最小堆栈顶部和新值中的最小值。

这是 Python 中的示例实现:

class MinStack:
  def __init__(self):
    self.values = []
    self.minimums = []

  def push(self,value):
    self.values.append(value)
    if len(self.minimums)==0:
      self.minimums.append(value)
    else:
      self.minimums.append(min(self.min(),value))

  def pop(self):
    self.minimums.pop()
    return self.values.pop()

  def min(self):
    return self.minimums[-1]