LeetCode 面试题 03.02. 栈的最小值

请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。

示例：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

由于要求的是都是 O(1) 的时间复杂度，目前还没想到，我目前想到的是：

1. 设置一个变量专门保存最小值，但是会存在一个问题，那就是如果 pop 操作的时候刚好移除的是最小值，那么就得需要从栈中重新寻找最小值，这个过程的时间复杂度为： O(n) ；
2. 如果我选择排好序，那么就会遇到第二个问题，那就是 push 的时候时间复杂度就为 O(n) 。

现在还不想看别人的答案，所以先保留在这里，等我想到了再编写出来。

来源：力扣（LeetCode）