在O(1)时间内检索堆栈中的Min元素

Question

我问这个问题的原因是因为我无法理解为什么我认为不能应用于这个特定问题的方式

"你如何设计一个堆栈,除了push和pop之外,还有一个返回最小元素的函数min？push,pop和min都应该在O(1)时间运行 "

我的基本解决方案:如果我们在堆栈类中有一个变量,那么每当我们将一个项目推送到堆栈时,我们会检查它是否小于我们的min变量.如果它将值赋给min,如果不是忽略.

你仍然可以获得最小函数的O(1);

int getMinimum(){
  return min;
}

为什么永远不会提到这个解决方案,或者我认为的方式有什么问题？

Answer 1

如果从堆栈中弹出数字,这将无效.

防爆.2,4,5,3,1.弹出1后,你的最低要求是多少？

解决方案是保持一堆最小值,而不仅仅是单个值.如果遇到的值小于当前最小值,则需要将其推入最小堆栈.

防爆.

Push(4):
Stack: 4
Min-stack: 4

Push(2):
Stack: 4 2
Min-stack: 4 2

Push(2):
Stack: 4 2 2
Min-stack: 4 2 2

Push(5):
Stack: 4 2 2 5
Min-stack: 4 2 2

Push(3):
Stack: 4 2 2 5 3
Min-stack: 4 2 2

Push(1):
Stack: 4 2 2 5 3 1
Min-stack: 4 2 2 1

Pop():
Stack: 4 2 2 5 3
Min-stack: 4 2 2

Pop():
Stack: 4 2 2 5
Min-stack: 4 2 2

Pop():
Stack: 4 2 2
Min-stack: 4 2 2

Pop():
Stack: 4 2
Min-stack: 4 2

Pop():
Stack: 4
Min-stack: 4