保存最小值得栈MinStack

问题&＃xff1a;

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Example:

MinStack minStack &＃61; new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.

解决&＃xff1a;

【注】要实现上面四个函数。

① 大体上与传统的stack相同&＃xff0c;不同的是getMin方法&＃xff0c;得到所有栈中数据的最小值&＃xff1b;使用两个栈&＃xff0c;一个保存正常数据&＃xff0c;另一个保存最小值。

public class MinStack { // 117ms
    private Stack s1 &＃61; new Stack<>();//直接存储
    private Stack s2 &＃61; new Stack<>();//存放每次比较时较小的数
    /** initialize your data structure here. */
    public MinStack() {}
    public void push(int x) {
        s1.push(x);
        if(s2.isEmpty() || s2.peek() >&＃61; x) s2.push(x);
    }
    public void pop() { //第一次POP出的数值若为最小值&＃xff0c;则它之下的一个数还是最小值&＃xff0c;也需要POP
        int x &＃61; s1.pop();
        if(s2.peek() &＃61;&＃61; x) s2.pop();
        //不能使用s2.peek() &＃61;&＃61; s1.peek()进行比较&＃xff0c;因为peek方法返回对象的类型是Object&＃xff0c;
        //使用&＃61;&＃61;比较无效&＃xff0c;因为它们返回的是两个不同的对象
    }
    public int top() {
        return s1.peek();
    }
    public int getMin() {
        return s2.peek();
    }
}
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj &＃61; new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 &＃61; obj.top();
 * int param_4 &＃61; obj.getMin();
 */

② 只使用栈保存数据&＃xff0c;使用一个变量保存最小值。

public class MinStack { // 147ms
    private Stack s &＃61; new Stack<>();
    private int minVal &＃61; Integer.MAX_VALUE;
    public MinStack(){}
    public void push(int x){
        if(x <&＃61; minVal){
            s.push(minVal);
            minVal &＃61; x;
        }
        s.push(x);
    }
    public void pop(){
        if(s.pop() &＃61;&＃61; minVal) minVal &＃61; s.pop();
    }
    public int top(){
        return s.peek();
    }
    public int getMin(){
        return minVal;
    }
}

③ 自己编写StackNode类&＃xff0c;在自己编写的stackNode中加入了最小值&＃xff0c;可以减少判断。

public class MinStack { //115ms
    StackNode head &＃61; null;
    /** initialize your data structure here. */
    public MinStack() {}
    public void push(int x) {
        if (head&＃61;&＃61;null){
            head &＃61; new StackNode(x,x);
        }else{
            StackNode newHead &＃61; new StackNode(x,Math.min(head.min,x));
            newHead.next &＃61; head;
            head &＃61; newHead;
        }
    }
    public void pop() {
        head &＃61; head.next;
    }
    public int top() {
        return head.val;
    }
    public int getMin() {
        return head.min;
    }
    class StackNode{
        int val;
        int min;
        StackNode next &＃61; null;
        public StackNode(int v,int min) {
            this.val &＃61; v;
            this.min &＃61; min;
        }
    }
}