请设计一个栈，除了常规栈支持的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) 的时间复杂度，目前还没想到，我目前想到的是：
- 设置一个变量专门保存最小值，但是会存在一个问题，那就是如果
pop操作的时候刚好移除的是最小值，那么就得需要从栈中重新寻找最小值，这个过程的时间复杂度为：O(n)； - 如果我选择排好序，那么就会遇到第二个问题，那就是
push的时候时间复杂度就为O(n)。
现在还不想看别人的答案，所以先保留在这里，等我想到了再编写出来。
来源：力扣（LeetCode）
网友评论