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

Question

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

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

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

那么我应该如何定义堆栈以满足要求呢？

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]

Answer 2

我就是这样做的。在实现栈的同时，修改node的定义为：

struct node
{
 int data;
 node *next;
 int min_so_far;
}

min_so_far保持它下面的所有节点的最小值，包括它自己。
所以当你插入一个新节点时，只需将当前节点的值与现有顶部节点的 min_so_far 值进行比较，并设置新节点的 min_so_far=min(顶部节点的 min_so_far,当前节点的值)

当你弹出时，你不需要做任何事情。

实现起来相当简单。

Answer 3

push您可以在ing 值时将最小值保存在堆栈变量中。如果pushed 值大于下一个push值，则将min变量设置为当前push值。

例如：

class _stack {
   int minValue;
   struct stackBucket{
      int data;
   }
   ....
   void push(int lastData){
       //push to the stack
       if(lastData < minValue) {
          minValue = lastData;
       }
  }
  int min(){ return minValue;}
};