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

我在互联网上看到一个算法问题，它说:

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

我知道 pop 和 push 的复杂度是 O(1)，但我不知道如何使 min 复杂度也成为 O(1) ，如果我定义一个变量来记住每次 push 时的最小数字，但是当 pop 时，最小数字也许会改变，所以我应该找到第二小的数字，这意味着 pop 复杂度不能是 O(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]

关于algorithm - 如何定义一个可以在 O(1) 内获得最小数字的堆栈，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17690643/