【题目】
【分析】
一般的栈就具有push()、pop()、top()的功能。getMin()的功能如何在常数时间内实现呢?
如果查找的话,至少是线性时间。不符合要求。
【方法一】
使用一个辅助栈,用来保存当前栈中的最小值。执行getMin()操作时,返回辅助栈的栈顶元素即可。
代码:
class MinStack {
Stack<Integer> dataStack;
Stack<Integer> minStack;
public MinStack() {
dataStack = new Stack();
minStack = new Stack();
}
public void push(int x) {
dataStack.push(x);
if(minStack.empty()==true || minStack.peek()>x){
minStack.push(x);
}else{
minStack.push(minStack.peek());
}
}
public void pop() {
dataStack.pop();
minStack.pop();
}
public int top() {
return dataStack.peek();
}
public int getMin() {
return minStack.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();
*/
结果:
【方法二】
也可以不使用辅助栈,让栈中保存的是<data,min>对,起到辅助栈相同的效果。
代码:
class MinStack {
class Node{
int data;
int min; //保存当前位置的最小值
Node(int data, int min){
this.data=data;
this.min = min;
}
}
Stack<Node> s;
public MinStack() {
s = new Stack<>();
}
public void push(int x) {
int min =x;
if(s.empty()==false && x>s.peek().min){
min = s.peek().min;
}
Node node = new Node(x,min);
s.push(node);
}
public void pop() {
s.pop();
}
public int top() {
return s.peek().data;
}
public int getMin() {
return s.peek().min;
}
}
/**
* 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();
*/
结果: