在 O(1) 时间内检索堆栈中的 Min 元素 [英] Retrieving the Min element in a stack in O(1) Time

问题描述

我问这个问题的原因是因为我不明白为什么我认为的方式不能应用于这个特定问题

The reason I'm asking this question is because I cannot see why the way I think cannot be applied to this particular question

你将如何设计一个堆栈，除了push和pop，还有一个函数min，它返回最小元素?push、pop 和 min 都应该在 O(1) 时间内运行"

我的基本解决方案:如果我们在 stack 类中有一个变量，那么当我们将一个项目推入堆栈时，我们会检查它是否有可能比我们的 min 变量小.如果是赋值给最小值，如果不是忽略.

My basic solution: Wouldn't it be possible if we had a variable in stack class, that whenever we were pushing an item to stack we would check if it is smaller than our min variable. If it is assign the value to the min, if not ignore.

你仍然会得到 O(1)，就像 min 函数一样；

You would still get the O(1) as the min function would be;

int getMinimum(){
  return min;
}

为什么从来没有提到这个解决方案，或者我的想法有什么问题?

Why this solution is never mentioned, or what is the fault with the way I think?

推荐答案

如果你从堆栈中弹出数字，这将不起作用.

This wouldn't work if you popped numbers off the stack.

例如.2,4,5,3,1.在您弹出 1 次后，您的最低限度是多少?

Ex. 2,4,5,3,1. After you pop 1 off, what is your minimum?

解决方案是保留一堆最小值，而不仅仅是一个值.如果遇到小于等于当前最小值的值，则需要将其压入最小堆栈.

The solution is to keep a stack of minimums, not just a single value. If you encounter a value that is less than equal to the current minimum, you need to push it onto the min-stack.

例如

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

这篇关于在 O(1) 时间内检索堆栈中的 Min 元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！