面试题 03.02. 栈的最小值

1.题目

请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。

3.代码

class MinStack {
    //定义两个值，等会在构造方法里面创建他们的对象，因为在main方法里面创建的是MinStack的对象
    //所以必须要在构造方法里面创建两个栈的对象，而定义却要在MinStack类里面，因为下面的其他方法还要用到这个对象
    Stack<Integer> stack;//普通的栈
     Stack<Integer> minstack;//里面栈顶的值就是最小值

    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
        minstack = new Stack<>();
  //      minstack.push(Integer.MAX_VALUE);//这里是可以用在另一个方法

    }
    
    //往栈里面添加元素，普通栈是一定要加的，最小值栈满足一定的条件再添加
    public void push(int x) {
        if(stack.empty() || x<=minstack.peek()){//满足普通栈是空的，要加入的元素比自己栈顶的元素还小
            minstack.push(x);
        }
        stack.push(x);

    }
    
    //往栈里面移除元素，就是出栈,普通栈是一定要出的，最小值栈满足条件再出
    public void pop() {
        if(stack.peek().equals(minstack.peek())){
            minstack.pop();
        }
        stack.pop();

    }
    
   //获得普通栈顶的元素
    public int top() {
        return stack.peek();

    }
    
    //获得最小值，就是最小值栈的栈顶
    public int getMin() {
        return minstack.peek();
        

    }
}