如何定义一个堆栈，使其能够在O(1)时间内获取最小值。

Question

如何定义一个堆栈，使其能够在O(1)时间内获取最小值。

3

我在网上看到一道算法题，题目如下：

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

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

那么我该如何定义这个栈来满足要求呢？

- hiway

最小的数字在哪里...是一个排序好的列表还是其他什么东西！ - Anirudha

3个回答

1

这是我的做法。在实现栈时，修改节点的定义如下：

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

min_so_far保存了包括它本身在内的所有节点的最小值。
因此，当您插入一个新节点时，只需将当前节点的值与现有顶部节点的min_so_far值进行比较，并设置新节点的min_so_far=min(顶部节点的min_so_far,当前节点的值)

弹出时，您无需执行任何操作。

这很容易实现。

- Aravind

你的方法似乎更简单。也许这里不需要 *next。 - hiway

@hiway：栈是通过链表实现的，因此我有下一个指针，尽管还有另一种实现方式，这里没有声明指针。 - Aravind

0

在编程中，当push一个值时，您可以将最小值保存在堆栈变量中。如果push的值大于下一个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;}
};

- Aniket Inge

1

这不是O(1)，而是O(n)。 - Anirudha

我的 min() 函数与堆栈中的元素数量无关。 - Aniket Inge

@Aniket，由于每次将元素推入堆栈时都要进行比较，因此它是O(n)的。对于n个元素，您将执行n次此操作。因此是O(n)。 - Srikar Appalaraju

1

@Aniket，如果minValue是栈的顶部元素，则在弹出时，minValue将无效。 - hiway

@hiway 是的，这就是我在 VaughnCato 的帖子中作为评论提到的。他的方法在 push 和 pop 方面效果更好。 - Aniket Inge

“pop” 会是什么样子？我认为你无法获得一个能够正确更新“minValue”的O(1)“pop”。考虑以下情况：push(2)，push(3)，push(3)，push(3)，push(1)，pop() - 在这个阶段，您将不得不遍历所有元素以找到最小值（2）。 - Bernhard Barker

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Vaughn Cato · Accepted Answer

只需使用另一个栈来存储最小值。当你向普通栈中推送一个值时，在min栈中也推送一个值。当你从普通栈中弹出一个值时，也要从min栈中弹出一个值。将要推送到min栈中的值将是当前min栈顶部和新值中的最小值。

以下是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]