辅助栈
除了存放数据的普通栈 stackData
,我们另外设置一个专门存放当前最小值的辅助单调栈 stackMin
。stackMin
中的值从栈底到栈顶单调不增。
当进行入栈操作时,如果入栈元素小于等于 stackMin
的栈顶元素,那么也将该元素在 stackMin
中入栈。这样一来,stackMin
的栈顶就始终记录着当前所有元素中的最小值,也即可以在 $O(1)$ 时间内取得最小值。
push
操作:stackData
正常入栈。如果stackMin
为空,或者待入栈元素小于等于stackMin
栈顶元素,则stackMin
也入栈。pop
操作:stackData
正常出栈。如果出栈元素与stackMin
栈顶元素相等,则stackMin
也出栈。top
操作:直接返回stackData
栈顶元素即可。getMin
操作:直接返回stackMin
栈顶元素即可。
时空复杂度
- 时间复杂度:$O(1)$
- 空间复杂度:$O(n)$
Java 代码
class MinStack {
Deque<Integer> stackData, stackMin;
/** initialize your data structure here. */
public MinStack() {
stackData = new LinkedList<>();
stackMin = new LinkedList<>();
}
public void push(int x) {
stackData.push(x);
if (stackMin.isEmpty() || x <= stackMin.peek()) {
stackMin.push(x);
}
}
public void pop() {
int x = stackData.pop();
if (x == stackMin.peek()) {
stackMin.pop();
}
}
public int top() {
return stackData.peek();
}
public int getMin() {
return stackMin.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/