题目描述
- 实现一个特殊的栈，在实现栈基本功能的基础上，再实现返回栈中最小元素的操作。
- 要求push，pop，getmin的操作时间复杂度都是 1。
- 设计的栈类型可以使用现成的栈结构。
解题尝试
- 自己最初的设想是在栈中增加一个成员变量min，用来记录最小值，每入栈一个元素就把这个元素和min比较，如果小于min就更新min的值。
- 但是如果值为min的那个最小元素出栈了，那么就无法判断当前栈中哪个元素最小，所以不可行。
解题方法1
- 除了实现基本功能的栈stack1之外，我们再定义一个栈stack2，用它来记录每一步的最小值。
- 当stack1入栈了一个元素x，我们比较x与stack2的栈顶元素top的大小，如果x<=top，将x入栈到stack2，否则不进行处理。
- 当stack1出栈一个元素（栈顶）x，我们比较x与stack2的栈顶元素top的大小，如果x==top，将stack2也出栈，否则不进行处理。
- 这样stack2的栈顶始终保存着stack1的最小值，实现getmin方法只需要返回stack2栈顶即可。
- 实现代码
class stack{
private Stack<Integer> stack1;
private Stack<Integer> stack2;
stack(){
this.stack1 = new Stack<>();
this.stack2 = new Stack<>();
}
public void push(int x){
this.stack1.push(x);
if(this.stack2.empty() || x<=this.stack2.peek()){
this.stack2.push(x);
}
}
public Integer pop(){
if(this.stack1.empty()){
throw new RuntimeException("stack empty");
}
int e = this.stack1.pop();
if(e == this.stack2.peek()){
this.stack2.pop();
}
return e;
}
public Integer getmin(){
if(this.stack2.empty()){
throw new RuntimeException("stack empty");
}
return this.stack2.peek();
}
}
解题方法2
- 可以发现解题方法1中栈stack2中的元素数量少于stack1中元素数量，这样每次出栈的时候都要将stack1的栈顶与stack2的栈顶比较一下。
- 我们也可以这样实现，在stack1入栈的时候，如果入栈元素x大于stack2的栈顶，就将stack2的栈顶再次入栈到stack2。这样可以使得stack2的元素数量与stack1是同步的，出栈的时候直接两个栈都进行出栈就好了。
- 代码如下：
class stack{
private Stack<Integer> stack1;
private Stack<Integer> stack2;
stack(){
this.stack1 = new Stack<>();
this.stack2 = new Stack<>();
}
public void push(int x){
this.stack1.push(x);
if(this.stack2.empty() || x<=this.stack2.peek()){
this.stack2.push(x);
}
if(x>this.stack2.peek()){
this.stack2.push(this.stack2.peek());
}
}
public Integer pop(){
if(this.stack1.empty()){
throw new RuntimeException("stack empty");
}
int e = this.stack1.pop();
this.stack2.pop();
return e;
}
public Integer getmin(){
if(this.stack2.empty()){
throw new RuntimeException("stack empty");
}
return this.stack2.peek();
}
}
- 两个方法的基本思路是一样的，都是使用stack2记录stack1每一步的最小值，两个方法的时间复杂度都为1，空间复杂度都为n。
- 唯一的区别是，方法1中stack2入栈时稍省空间，出栈时稍费时间。方法2中stack2入栈时稍费空间，入栈时稍省时间。