本文共 1231 字，大约阅读时间需要 4 分钟。

/** * 实现一个栈，该栈有出栈（pop），入栈（push）、取最小元素（getMin）3个方法。要保证3个方法都是O（1） * 解法：借助辅助栈，解法见代码说明 * 时间复杂度均为O(1)，最大空间复杂度为O(n) */public class MinStack {    private Stack
   
     mainStack = new Stack();    private Stack
    
      minStack = new Stack();    /**     * 入栈操作     * @param data     */    public void push(int data){        mainStack.push(data);        //如果辅助栈为空，或者新元素小于或等于辅助栈栈顶，则将新元素压入到辅助栈        if(minStack.isEmpty() || minStack.peek() > data){            minStack.push(data);        }    }    /**     * 出栈操作     */    public Integer pop(){        //如果出栈元素和辅助栈元素值相等，辅助栈出栈        if(mainStack.peek().equals(minStack.peek())){            minStack.pop();        }       return mainStack.pop();    }    /**     * 获取栈中最小数     * @return     */    public Integer getMin(){        if(!minStack.isEmpty()){            return minStack.peek();        }        return null;    }    public static void main(String[] args) {        MinStack stack = new MinStack();        stack.push(4);        stack.push(9);        stack.push(7);        stack.push(3);        stack.push(8);        stack.push(5);        System.out.println(stack.getMin());        stack.pop();        stack.pop();        stack.pop();        System.out.println(stack.getMin());    }}
    
   

转载地址：http://sqsvi.baihongyu.com/