请设计一个栈,除了常规栈支持的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.
方法一:
使用辅助栈。定义两个栈,stack1, stakc2(辅助栈)
- stack2栈用于存储stack1中对应元素的下面的元素的最小值。
- 每入栈一个元素,再stack2中,对应位置,判断一下,它和之前辅助栈中的元素谁更小,然后更新辅助栈中的元素。
- 这样就可以让stack2栈中的元素与stack1一一对应,并且是以当前元素为栈顶的栈中的最小值。
代码:
class MinStack {
Deque<Integer> stack1, stack2;
/** initialize your data structure here. */
public MinStack() {
stack1 = new LinkedList<>();
stack2 = new LinkedList<>();
}
public void push(int x) {
stack1.addLast(x);
if (stack2.isEmpty()) stack2.addLast(x);
else {
stack2.addLast(Math.min(x, stack2.getLast()));
}
}
public void pop() {
stack1.removeLast();
stack2.removeLast();
}
public int top() {
return stack1.getLast();
}
public int getMin() {
return stack2.getLast();
}
}
时间复杂度:O(1)
空间复杂度:O(n)