1-1 带有getmin功能的栈

题目描述

• 实现一个特殊的栈，在实现栈基本功能的基础上，再实现返回栈中最小元素的操作。
• 要求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入栈时稍费空间，入栈时稍省时间。