定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例1:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.
提示:
辅助栈:数据栈再压入元素的时候与辅助栈的顶层元素(即之前数据栈的最小元素)做比较,如果比它小,就把值x同时压入数据栈和辅助栈。如果比它大,说明此时最小元素仍然是之前的最小元素,把辅助栈的栈顶取出来,数据栈压入x,辅助栈压入原本的辅助栈栈顶元素。这样就能保证辅助栈始终存放当前数据栈的最小值,在弹出数据时,同时弹出数据栈和辅助栈栈顶
class MinStack {
private Stack<Integer> stack_data;
private Stack<Integer> stack_min;
/** initialize your data structure here. */
public MinStack() {
stack_data = new Stack<>();
stack_min = new Stack<>();
}
public void push(int x) {
stack_data.push(x);
if(stack_min.size()==0||x<stack_min.peek())
stack_min.push(x);
else
stack_min.push(stack_min.peek());
}
public void pop() {
stack_data.pop();
stack_min.pop();
}
public int top() {
return stack_data.peek();
}
public int min() {
return stack_min.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.min();
*/