我要问这个问题的原因是因为我不明白为什么我的思维方式不能适用于这一特定问题

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，还有另外一种功能分返回最小的元素？ PUSH，POP和最小值都应该运行在O（1）时间

"How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time"

我的基本解决方案：那岂不是可能的，如果我们在一个变量堆栈类，每当我们推一个项目堆栈，我们会如果检查为较小比我们的分的变量。如果是赋值给分，如果不能忽视。

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）作为最小功能会;

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